:)

Time limit: 1s Memory limit: 64MB Input: Output:

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

Cerință

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

  • se aleg 2 numere ii și xx astfel încât 1iN1 \leq i \leq N și se înlocuiește aia_i cu xx.

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

Date de intrare

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

Date de ieșire

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

Restricții și precizări

  • 1t1041 \leq t \leq 10^4
  • 1N21051 \leq N \leq 2 \cdot 10^5
  • 0Ai109 0 \leq A_i \leq 10^9
  • Se garantează faptul că suma NN-urilor pe toate testcase-urile este 2105\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 xrxr din primul test case arată în felul următor: 1,2,21,2,2. Dacă alegem i=3i = 3 și x=4x = 4, atunci vectorul xrxr va arăta așa: 1,2,61,2,6.

În al 33-lea test case vectorul xrxr are deja toate elementele distincte.

Log in or sign up to be able to send submissions!