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