You are given an array $A$ consisting of $N$ distinct integers. If the size of the array is greater than one, then you can perform the following operations any number of times:

• Select two integers $A_i$ and $A_j$ such that $CountOnes(A_i \oplus A_j) = 1$ and delete either $A_i$ or $A_j$ from the array. This operation costs $C_1$.

• Select two integers $A_i$ and $A_j$ such that $CountOnes(A_i \oplus A_j) \gt 1$ and delete either $A_i$ or $A_j$ from the array. This operation costs $C_2$.

Here, $CountOnes(X)$ returns the number of $1s$ available in the binary representation of integer $X$. Determine the minimum cost to reduce the size of the array to $1$.

Input format

• First line: $T$ denoting the number of test cases
• For each test case:
  • First line: $N$
  • Second line: Two space-separated integers $C_1$ and $C_2$
  • Third line: $N$ space-separated integers denoting the array $A$

Output format

For each test case, print a single integer in a separate line as described in the problem statement

Constraints

$1 \le T \le 20$

$1\le N\le 10^4$

$1 \le C_1,C_2,A_i \le 10^9$

Subtasks

• For 10 points: $1 \le N \le 10$
• For 90 points: Implement the original constraints