Description

Larutan gives Natural a multiset of $n$ positive integers. A multiset may contain multiple occurrences of the same value.

Natural may perform either of the following operations any number of times:

1. If the multiset contains at least two occurrences of a value $x$, delete one occurrence of $x$. This operation costs $x$ units of time.
2. Choose one occurrence of a value $x$ and replace it with $\lfloor\sqrt{x}\rfloor$. This operation costs $C$ units of time.

Values produced by the second operation are also part of the multiset and may be used in subsequent operations.

Determine the minimum total time required to reduce the multiset to exactly one remaining element.

Input Format

The first line contains one integer $T$, the number of test cases.

Each test case consists of two lines:

• The first line contains three integers $n$, $V$, and $C$, where $n$ is the number of elements, $V$ is an upper bound on their values, and $C$ is the cost of one replacement operation.
• The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing the initial multiset.

Output Format

For each test case, output the minimum total time on a separate line.

Sample

Input #1

1
5 10 3
1 1 3 5 5

Output #1

17

Sample Explanation

Consider the initial multiset $\{1,1,3,5,5\}$.

Perform the following operations:

1. Delete one occurrence of $5$. The multiset becomes $\{1,1,3,5\}$, at a cost of $5$.
2. Replace $5$ with $\lfloor\sqrt{5}\rfloor=2$. The multiset becomes $\{1,1,2,3\}$, at a cost of $3$.
3. Replace $3$ with $\lfloor\sqrt{3}\rfloor=1$. The multiset becomes $\{1,1,1,2\}$, at a cost of $3$.
4. Replace $2$ with $\lfloor\sqrt{2}\rfloor=1$. The multiset becomes $\{1,1,1,1\}$, at a cost of $3$.
5. Delete one occurrence of $1$. The multiset becomes $\{1,1,1\}$, at a cost of $1$.
6. Delete one occurrence of $1$. The multiset becomes $\{1,1\}$, at a cost of $1$.
7. Delete one occurrence of $1$. The multiset becomes $\{1\}$, at a cost of $1$.

The total cost is $5+3+3+3+1+1+1=17$, which is the minimum possible cost.

Constraints

For all test cases:

• $1\leq T\leq 5$;
• $1\leq n$ and the sum of $n$ over all test cases does not exceed $10^3$;
• $1\leq a_i\leq V$;
• $1\leq V\leq 10^{12}$;
• $1\leq C\leq 10^{10}$.