You are given an array $A_{1}, A_{2}, \dots, A_{N}$ consisting of N integers. Your goal is to make the GCD of all the elements in the array an odd integer. To achieve this goal, you can do the following operation any number of times:

Choose an index i\;(1≤ i ≤ N) such that A_{i} > 1 and set $A_{i} = \lfloor \frac{A_{i}}{2}$\ $\rfloor$

You can choose an index multiple times during the operations. Find the minimum number of operations after which GCD of all the elements in the array becomes an odd integer.

Note: $\lfloor x \rfloor$ : Returns the largest integer that is less than or equal to x (i.e rounds down to the nearest integer). For example$, \lfloor 1.5 \rfloor = 1, \lfloor 2 \rfloor = 2, \lfloor \frac{7}{2}$\ $\rfloor$ $;= \lfloor 3.5 \rfloor$ \;= 3.

------ Input Format ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$.

------ Output Format ------

For each test case, print a single line containing one integer - the minimum number of operations after which GCD of all the elements in the array becomes an odd integer.

------ Constraints ------

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $5\cdot10^{5}$

----- Sample Input 1 ------
3
3
2 3 5
2
4 6
3
4 12 24
----- Sample Output 1 ------
0
1
2
----- explanation 1 ------
Test case $1$: The GCD of all integers in the array is already $1$, which is odd.

Test case $2$: You choose the index $i = 2$ and set $A_{2} = \lfloor \frac{6}{2}\ \rfloor = \lfloor 3 \rfloor = 3$. So the array becomes $[4, 3]$ and the GCD of $4$ and $3$ is $1$.

见题面

见题面