H. Optimal Balancing Strategy
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array of positive integers $$$A$$$ of size $$$n$$$. In one operation, you may perform the following:

  • Choose any indices $$$i, j$$$ such that $$$1 \le i, j \le n$$$,
  • Choose a positive integer $$$p$$$ that divides $$$A_i$$$, formally, $$$p \mid A_i$$$,
  • Update $$$A_i := \frac{A_i}{p}$$$,
  • Update $$$A_j := A_j \cdot p$$$.
Each of the operation has a cost of $$$p$$$.

After performing the operation any number of times (possibly zero), the final array must satisfy the following requirements, one from each of your three friends:

  • Muhaimin wants at least $$$a$$$ elements to be evenly even. A positive integer is called evenly even if it has no odd prime factor.
  • Noshin wants at least $$$b$$$ elements to be oddly odd. A positive integer is called oddly odd if it has no even prime factor.
  • Osman wants the whole array to be balanced. An array is called balanced if each element of the array is either evenly even, or oddly odd, or both. For example, [4, 27] is a balanced array, while [6, 9] is not.

Determine the minimum total cost required to satisfy all three requirements. It can be proved that it is always possible to satisfy all three requirements.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 500)$$$ — the number of test cases.

The first line of each test case contains three space-separated integers $$$n$$$, $$$a$$$ and $$$b$$$ $$$(2 \le n \le 2 \cdot 10^5, 1 \le a, \space b \le (n - 1), 2 \le a + b \le n)$$$ — the size of the array, the minimum required number of evenly even elements and the minimum required number of oddly odd elements respectively.

The third line of each test case contains $$$n$$$ integers $$$A_1, A_2, \dots, A_n$$$ $$$(1 \le A_i \le 10^6)$$$ — the elements of the array initially.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer in a line — the minimum total cost required to make the array balanced with at least $$$a$$$ evenly even and at least $$$b$$$ oddly odd elements.

Example
Input
3
8 3 3
6 10 12 14 18 20 22 24
3 1 1
8 4 4
5 2 3
2 3 5 8 13
Output
21
4
0
Note

In the second test case, we can choose $$$i = 2$$$, $$$j = 1$$$ and $$$p = 4$$$ (divide $$$A_2$$$ by $$$4$$$ and multiply $$$A_1$$$ by $$$4$$$), resulting in the array $$$[32, 1, 4]$$$.

Other possible final arrays with the same minimum cost are:

  • $$$[8, 1, 16]$$$
  • $$$[32, 4, 1]$$$
  • $$$[8, 16, 1]$$$