An array is called good if every element of the array is an even integer.
You are given an array A of length N. In one move, you can do one of the following operations:

• Choose an index i and set \(A_i =\lfloor \frac{A_i}{2} \rfloor\)
• Choose an index \(1 \le i \lt \mid A\mid\)and replace \(A_i, A_{i+1}\) with one occurrence of \(A_i \oplus A_{i+1}\). Here \(\mid A \mid\) denotes the length of the array A and \(\oplus\) denotes bitwise XOR operation.

Find the minimum number of moves needed to make array A good.

Input format

• The first line contains T denoting the number of test cases. The description of T test cases is as follows:
• For each test case:
  • The first line contains N denoting the size of array A.
  • The second line contains N space-separated integers \(A_1, A_2, \dots, A_N\) - denoting the elements of A.

Output format
For each test case, print the minimum number of moves needed to make array A good.

Constraints