Non Zero Xor Codechef Solution

Problem

An array $A$ of size $N$ is called good if the following conditions hold:

• For every pair $(l,r)$ $(1\le l\le r\le N)$, A_l \oplus A_{l+1} \oplus … \oplus A_{r} \ne 0Al​⊕Al+1​⊕…⊕Ar​=0. (where $\oplus$ denotes the bitwise XOR operation.)

JJ has an array $A$ of size $N$. He wants to convert the array to a good array. To do so he can perform the following operation multiple times:

• Pick an index $i$ such that $(1\le i\le N)$ and set A_i := XAi​:=X where 0 \le X \lt 10^{10^{10}}0≤X<101010.

Find the minimum number of operations required to convert $A$ into a good array.

Input Format

• The first line contains $T$ – the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ – the size of the array $A$.
• The second line of each test case contains $N$ space-separated integers A_1, A_2, \dots, A_NA1​,A2​,…,AN​ denoting the array $A$.

Output Format

For each test case, output the minimum number of operations required to convert the array $A$ into a good array.

Constraints

Sample 1:

3
5
1 2 3 4 4
3
0 0 0
6
2 3 5 7 11 13

2
3
0

Explanation:

Test Case 1: We can set A_2 = 4A2​=4 and A_4 = 5A4​=5. Thereby $A$ will become $[1,4,3,5,4]$ which is good. We can prove that we can not make $A$ good in $<2$ operations.

Test Case 2: We can set A_1 = 1A1​=1, A_2 = 10A2​=10 and A_3 = 100A3​=100. Thereby $A$ will become $[1,10,100]$ which is good. We can prove that we can not make $A$ good in $<3$ operations.

Test Case 3: The given array $A$ is already good.