RoAlgo Educational Round #3 | :)

Numim un vector $A$ cu $N$ elemente $\textbf{bun}$ dacă sumele xor pe prefixe constituie un vector cu elemente distincte. Formal, dacă $xr_i = A_1 \oplus A_2 \oplus \dots \oplus A_i$ (aici, semnul $\oplus$ reprezintă operația xor), atunci vectorul $xr$ conține exact $N$ elemente distincte.

Cerință

Se dă un vector $A$ și un număr $N$, vreți să-l faceți $\textbf{bun}$ folosind un număr oarecare (posibil $0$) de operații de următorul tip:

• se aleg 2 numere $i$ și $x$ astfel încât $1 \leq i \leq N$ și se înlocuiește $a_i$ cu $x$.

Aflați numărul minim de operații necesare ca să transformați vectorul într-un vector $\textbf{bun}$.

Date de intrare

Pe prima linie se află $t$ (numărul de test cases). Pe prima linie a fiecărui test case se află un număr $N$, iar pe următoarea linie se află exact $N$ numere separate prin câte un spațiu.

Date de ieșire

Se vor afișa $t$ linii, răspunsurile la cele $t$ test case-uri.

Restricții și precizări

• $1 \leq t \leq 10^4$
• $1 \leq N \leq 2 \cdot 10^5$
• $0 \leq A_i \leq 10^9$
• Se garantează faptul că suma $N$-urilor pe toate testcase-urile este $\leq 2 \cdot 10^5$.

Exemplu

stdin

4
3
1 3 0
2
0 0 
3
1 2 3
10
100 34 2 4 1 5 0 12 9 10

stdout

1
1
0
2

Explicație

Vectorul $xr$ din primul test case arată în felul următor: $1,2,2$. Dacă alegem $i = 3$ și $x = 4$, atunci vectorul $xr$ va arăta așa: $1,2,6$.

În al $3$-lea test case vectorul $xr$ are deja toate elementele distincte.