An array A of size N is called *good* if the following conditions hold:
For every pair (l, r) (1 ≤ l ≤ r ≤ N), A_{l} \oplus A_{l+1} \oplus ... \oplus A_{r} \ne 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 ≤ i ≤ N) and set A_{i} := X where 0 ≤ X < 10^{10^{10}}.

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_{N} 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 ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} < 2^{30}$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
5
1 2 3 4 4
3
0 0 0
6
2 3 5 7 11 13

----- Sample Output 1 ------ 
2
3
0

----- explanation 1 ------ 
Test Case 1: We can set $A_{2} = 4$ and $A_{4} = 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} = 1$, $A_{2} = 10$ and $A_{3} = 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*.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Range queries

Greedy algorithms
Skill types: Range queries

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = {0}
	(x, ans) = (0, 0)
	for i in range(n):
		x = x ^ l[i]
		if x in s:
			ans += 1
			s = {l[i]}
			x = l[i]
		else:
			s.add(x)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = {0}
	ans = 0
	pref = 0
	for x in a:
		pref ^= x
		if pref in p:
			ans += 1
			pref = x
			p = {x}
		else:
			p.add(pref)
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = {0}
	p = 0
	m = 0
	for i in a:
		p = p ^ i
		if p in s:
			m += 1
			p = i
			s = {i}
		else:
			s.add(p)
	print(m)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	temp = {0}
	count = 0
	m = 0
	for i in l:
		m ^= i
		if m in temp:
			count += 1
			m = i
			temp = {i}
		else:
			temp.add(m)
	print(count)


t = int(input())
for s in range(t):
	a = int(input())
	arr = [int(i) for i in input().split()]
	s = set()
	s.add(0)
	x = 0
	ans = 0
	for i in arr:
		x = x ^ i
		if x in s:
			ans += 1
			s.clear()
		s.add(x)
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(k, t) = (0, 0)
	m = {}
	m[0] = 1
	for j in l:
		t ^= j
		if t in m and m[t] == 1:
			k += 1
			m.clear()
		m[t] = 1
	print(k)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	dic = {}
	(temp, ans) = (0, 0)
	dic[0] = 1
	for i in range(n):
		temp ^= a[i]
		if temp in dic and dic[temp] == 1:
			ans += 1
			dic.clear()
		dic[temp] = 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	temp = 0
	d[0] = 1
	ans = 0
	for i in range(n):
		temp ^= a[i]
		if temp in d:
			ans += 1
			d.clear()
		d[temp] = 1
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	a = 0
	temp = 0
	d = {}
	d[0] = 1
	for i in A:
		temp ^= i
		if temp in d and d[temp] == 1:
			a += 1
			d = 0
			d = {}
		d[temp] = 1
	print(a)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	temp = 0
	d = {}
	d[0] = 1
	for i in l:
		temp ^= i
		if temp in d and d[temp] == 1:
			ans += 1
			d = {}
		d[temp] = 1
	print(ans)


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	(y, xor) = (0, 0)
	d = set([0])
	for i in a:
		if xor ^ i in d:
			xor = 0
			y += 1
			d = set([0])
		else:
			xor = xor ^ i
			d.add(xor)
	print(y)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	a = 0
	x = 0
	Sum1 = set([0])
	for i in A:
		if x ^ i in Sum1:
			a += 1
			x = 0
			Sum1 = set([0])
		else:
			x = x ^ i
			Sum1.add(x)
	print(a)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	(ans, xor) = (0, 0)
	xorSums = set([0])
	for i in A:
		if xor ^ i in xorSums:
			ans += 1
			xor = 0
			xorSums = set([0])
		else:
			xor = xor ^ i
			xorSums.add(xor)
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(ans, xor) = (0, 0)
	xorSums = set([0])
	for i in a:
		if xor ^ i in xorSums:
			ans += 1
			xor = 0
			xorSums = set([0])
		else:
			xor = xor ^ i
			xorSums.add(xor)
	print(ans)


t = int(input())
for i in range(t):
	a = int(input())
	l = list(map(int, input().split()))
	s = {0}
	b = 0
	x = 0
	for i in l:
		x ^= i
		if x in s:
			b += 1
			x = i
			s = {i}
		else:
			s.add(x)
	print(b)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = {0}
	a = 0
	res = 0
	for i in l:
		a ^= i
		if a in s:
			res += 1
			a = i
			s = {i}
		else:
			s.add(a)
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	temp = 0
	ans = 0
	d = {0: True}
	for i in range(n):
		temp ^= a[i]
		if temp in d:
			ans += 1
			d = dict()
		d[temp] = True
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	s = {0}
	count = 0
	p = 0
	for i in range(n):
		p = p ^ l[i]
		if p not in s:
			s.add(p)
		else:
			count += 1
			s = {p}
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	curr = 0
	ans = 0
	d = {0: True}
	for i in range(len(arr)):
		curr ^= arr[i]
		if curr in d:
			ans += 1
			d = dict()
		d[curr] = True
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = {0}
	c = 0
	p = 0
	for i in l:
		p ^= i
		if p in s:
			c += 1
			p = i
			s = {i}
		else:
			s.add(p)
	print(c)


def Solution(n, a):
	count = 0
	temp = {0}
	p = 0
	for i in range(n):
		p = p ^ a[i]
		if p not in temp:
			temp.add(p)
		else:
			count += 1
			temp = {p}
	return count
test = int(input())
for t in range(test):
	n = int(input())
	a = tuple(map(int, input().split()))
	print(Solution(n, a))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = {0}
	pref = 0
	ans = 0
	for x in l:
		pref ^= x
		if pref in p:
			ans += 1
			pref = x
			p = {x}
		else:
			p.add(pref)
	print(ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	s = {0}
	t = 0
	c = 0
	for i in l:
		t ^= i
		if t in s:
			c += 1
			s.clear()
		s.add(t)
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = 0
	ans = 0
	d = {0: True}
	for i in range(n):
		temp ^= arr[i]
		if temp in d:
			ans += 1
			d = dict()
		d[temp] = True
	print(ans)


n = int(input())
for i in range(n):
	x = int(input())
	y = list(map(int, input().split()))
	k = 0
	c = 0
	t = {0}
	for i in y:
		k ^= i
		if k in t:
			c += 1
			k = i
			t = {i}
		else:
			t.add(k)
	print(c)


from collections import defaultdict

class T:

	def solve(self):
		n = int(input())
		a = list(map(int, input().split()))
		d = defaultdict(int)
		ans = 0
		xor = 0
		d[0] = 1
		for i in range(n):
			xor ^= a[i]
			if xor in d:
				ans += 1
				d.clear()
			d[xor] += 1
		return ans
for t in range(int(input())):
	obj = T()
	print(obj.solve())


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	pset = {0}
	p = 0
	c = 0
	for i in b:
		p ^= i
		if p in pset:
			c += 1
			p = i
			pset = {i}
		else:
			pset.add(p)
	print(c)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	pset = {0}
	hprev = 0
	count = 0
	for i in b:
		hprev ^= i
		if hprev in pset:
			count += 1
			hprev = i
			pset = {hprev}
		else:
			pset.add(hprev)
	print(count)


from collections import defaultdict
from collections import defaultdict, deque, Counter
from itertools import groupby, accumulate, cycle, chain
from bisect import bisect_left, bisect_right
from math import inf
from string import ascii_lowercase, ascii_uppercase
from copy import deepcopy
from heapq import heapify, heappush, heappop
from functools import lru_cache
import re
T = int(input())
vt = lambda t: [t(num) for num in input().split()]
it = lambda : vt(int)[0]
st = lambda a: a.sort()

def run_tc():
	n = it()
	arr = vt(int)
	ans = x = 0
	s = set([0])
	for i in range(n):
		x ^= arr[i]
		if x in s:
			ans += 1
			x = arr[i]
			s = set([x])
		else:
			s.add(x)
	return ans
for _ in range(T):
	print(run_tc())


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	(ans, pref) = (0, 0)
	s = {0}
	for i in l:
		pref ^= i
		if pref in s:
			ans += 1
			pref = i
			s = {pref}
		else:
			s.add(pref)
	print(ans)


from operator import xor
R = lambda : map(int, input().split())
(t,) = R()
speed = lambda d, t: float(d) / t
for _ in range(t):
	(n,) = R()
	arr = list(R())
	for i in range(1, n):
		arr[i] ^= arr[i - 1]
	ans = 0
	myMap = {0}
	for val in arr:
		if val in myMap:
			ans += 1
			myMap = {val}
		else:
			myMap.add(val)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(1, n):
		arr[i] ^= arr[i - 1]
	s = {0}
	res = 0
	for e in arr:
		if e in s:
			res += 1
			s = {e}
		else:
			s.add(e)
	print(res)


def main():
	T = int(input())
	for counter in range(T):
		ans = 0
		n = int(input())
		a = list(map(int, input().split()))
		present = {0}
		prefix = 0
		for x in a:
			prefix ^= x
			if prefix in present:
				ans += 1
				prefix = x
				present = {x}
			else:
				present.add(prefix)
		print(ans)
main()


def ans(arr):
	k = {0}
	current = 0
	c = 0
	for y in arr:
		xored = current ^ y
		if xored in k:
			c += 1
			k = {y}
			current = y
		else:
			current = xored
			k.add(xored)
	return c
test_cases = int(input())
while test_cases != 0:
	d_ = input()
	d = list(map(int, input().split()))
	print(ans(d))
	test_cases -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set()
	s.add(0)
	x = 0
	ans = 0
	for i in range(n):
		x = x ^ a[i]
		if x in s:
			ans += 1
			x = a[i]
			s = set()
			s.add(x)
		else:
			s.add(x)
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	l = list(map(int, input().split(' ')))
	count = 0
	v = 0
	d = {}
	d[v] = 0
	for i in l:
		v ^= i
		if v in d:
			count += 1
			d = {}
			v = 0
		d[v] = 1
	print(count)


def solve(n, arr):
	lookup = {0}
	curr = 0
	res = 0
	for num in arr:
		curr ^= num
		if num == 0 or curr in lookup:
			lookup = {0}
			curr = 0
			res += 1
			continue
		lookup.add(curr)
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	dic = {}
	c = 0
	for i in range(n):
		x = x ^ a[i]
		if x in dic or a[i] == 0 or x == 0:
			c += 1
			dic = {}
			x = 0
		else:
			dic[x] = 1
	print(c)


import time
import sys
import math
input = sys.stdin.readline
(mod, infi) = (1000000007, sys.maxsize)
from collections import deque, Counter, defaultdict as dd
from heapq import heappop, heappush, heapify
from itertools import accumulate
from functools import lru_cache, reduce
from operator import mul, add, sub, truediv, floordiv, lt, le, eq, ne, gt, xor, concat, getitem, pow, lshift
inty = lambda : int(input())
stringy = lambda : input().strip()
normal = lambda : input().split()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
tick = lambda : time.perf_counter()
logg = lambda a, b: math.log2(a) / math.log2(b)
acc = lambda x: list(accumulate(x))
sign = lambda x, y: x >= 0 and y >= 0 or (x < 0 and y < 0)
T = inty()
for _ in range(T):
	n = inty()
	a = listy()
	seen = set()
	xor = 0
	res = 0
	for num in a:
		xor ^= num
		if xor in seen or num == 0 or xor == 0:
			res += 1
			xor = 0
			seen.clear()
		else:
			seen.add(xor)
	print(res)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	curx = 0
	s = {0}
	for j in range(n):
		curx ^= arr[j]
		if curx in s:
			ans += 1
			curx = arr[j]
			s = {arr[j]}
		else:
			s.add(curx)
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	arr = [int(_) for _ in input().split()]
	prefix = [0]
	ans = curr_xor = 0
	for i in range(n):
		curr_xor ^= arr[i]
		if curr_xor in prefix:
			ans += 1
			curr_xor = arr[i]
			prefix = [arr[i]]
		else:
			prefix.append(curr_xor)
	print(ans)


for _ in range(int(input())):
	k = int(input())
	l = list(map(int, input().split()))
	kl = {0: 1}
	cnt = 0
	rmn = 0
	for i in l:
		rmn ^= i
		if rmn in kl:
			kl = {0: 1}
			cnt += 1
			rmn = 0
		else:
			kl[rmn] = 1
	print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	check = {0}
	xor = 0
	count = 0
	for i in arr:
		xor ^= i
		if xor in check:
			count += 1
			xor = i
			check = {i}
		else:
			check.add(xor)
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	xor = 0
	set_ = set()
	set_ = {xor}
	count = 0
	for i in range(0, n):
		xor = a[i] ^ xor
		if xor in set_:
			xor = 0
			count += 1
			set_.clear()
			set_.add(xor)
		else:
			set_.add(xor)
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = {0}
	ans = 0
	pre = 0
	for x in a:
		pre ^= x
		if pre in p:
			ans += 1
			pre = x
			p = {x}
		else:
			p.add(pre)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	c1 = 0
	p = [0]
	for i in l:
		c1 ^= i
		if c1 in p:
			c += 1
			c1 = i
			p = [i]
		else:
			p.append(c1)
	print(c)


for _ in range(int(input())):
	xrs = set([0])
	n = int(input())
	a = [int(i) for i in input().split()]
	prv = 0
	ct = 0
	for i in range(n):
		xr = prv ^ a[i]
		if xr in xrs:
			ct += 1
			xrs = set([xr])
		else:
			xrs.add(xr)
		prv = xr
	print(ct)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(res, A) = (0, 0)
	s = set()
	s.add(A)
	for i in a:
		A = A ^ i
		if A in s:
			res += 1
			A = 0
			s.clear()
		s.add(A)
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	xor = 0
	set1 = set()
	set1.add(0)
	for i in arr:
		xor = xor ^ i
		if xor in set1:
			count += 1
			xor = 0
			set1.clear()
		set1.add(xor)
	print(count)


import sys
from itertools import islice
for s in islice(sys.stdin, 2, None, 2):
	r = t = 0
	a = {0}
	for x in s.split():
		t ^= int(x)
		if t in a:
			r += 1
			t = 0
			a = {0}
		a.add(t)
	print(r)


for test in range(int(input())):
	n = int(input())
	a = [int(ai) for ai in input().split()]
	switched = 0
	seen = {0}
	xor = 0
	for i in range(n):
		xor ^= a[i]
		if xor in seen:
			switched += 1
			seen = {0}
			xor = 0
		seen.add(xor)
	print(switched)


t = int(input())

def fn(arr):
	l = len(arr)
	stack = []
	operations = 0
	for i in range(l):
		if arr[i] == 0:
			operations += 1
			stack = []
		elif arr[i] in stack:
			operations += 1
			stack = []
		else:
			for j in range(len(stack)):
				stack[j] = stack[j] ^ arr[i]
			stack.append(arr[i])
	print(operations)
for _ in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()))
	fn(arr1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = set()
	s.add(0)
	(ct, xrl) = (0, 0)
	for i in range(n):
		xrl ^= arr[i]
		if list(s).count(xrl) >= 1:
			s.clear()
			ct += 1
			s.add(0)
			xrl = 0
		s.add(xrl)
	print(ct)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, nums):
		self._size = len(nums)
		self._tree = [0] * (4 * self._size)
		self.build(nums)

	def build(self, a, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if lo == hi:
			self._tree[v] = a[lo]
		else:
			mi = (lo + hi) // 2
			self.build(a, 2 * v, lo, mi)
			self.build(a, 2 * v + 1, mi + 1, hi)
			self._tree[v] = self._tree[2 * v] + self._tree[2 * v + 1]

	def update(self, pos, val, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if lo == hi:
			self._tree[v] = val
		else:
			mi = (lo + hi) // 2
			if pos <= mi:
				self.update(pos, val, 2 * v, lo, mi)
			else:
				self.update(pos, val, 2 * v + 1, mi + 1, hi)
			self._tree[v] = self._tree[2 * v] + self._tree[2 * v + 1]

	def query(self, l, h, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if l > h:
			return 0
		elif l == lo and h == hi:
			return self._tree[v]
		else:
			mi = (lo + hi) // 2
			return self.query(l, min(mi, h), 2 * v, lo, mi) + self.query(max(mi + 1, l), h, 2 * v + 1, mi + 1, hi)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	mapp = {}
	x = 0
	ans = set()
	for i in range(n):
		x ^= a[i]
		if x in mapp or a[i] == 0 or x == 0:
			ans.add(i)
			x = 0
			mapp = {}
		else:
			mapp[x] = i
	print(len(ans))
for t in range(int(input())):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	res = 0
	d[0] = 1
	curr = 0
	for i in range(len(arr)):
		curr = curr ^ arr[i]
		if curr in d:
			res += 1
			d = {}
			curr = 0
		d[curr] = 0
	print(res)


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr: enumerate(itr)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def solve(*args, **kwargs):
	(n, arr) = args
	cnt = res = 0
	hshst = {0}
	for (idx, ele) in enum(arr):
		cnt ^= ele
		if cnt in hshst:
			res += 1
			hshst.clear()
			cnt = 0
			hshst.add(0)
		hshst.add(cnt)
	return res

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp(int)
		arg3 = inp_vars(int, SPACE)
		res = solve(*(arg1, arg3))
		if type(res) in {list, tuple, set}:
			print(*res, sep='\n')
		else:
			print(res)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	iop = 0
	st = set()
	st.add(0)
	for i in range(n):
		iop ^= a[i]
		if list(st).count(iop) >= 1:
			st = set()
			count += 1
			st.add(0)
			iop = 0
		set(st)
		st.add(iop)
	print(count)


T = int(input())
for _ in range(T):
	st = set([])
	st.add(0)
	flag = 0
	N = int(input())
	arr = list(map(int, input().split()))
	xor1 = 0
	marker = 5000
	c = 0
	bool = True
	marker = flag
	for i in range(N):
		flag += 1
		xor1 ^= arr[i]
		marker -= flag * 2
		if xor1 in st:
			bool = False
			st.clear()
			c += 1
			st.add(0)
			marker -= 1
			xor1 = 0
		bool = False
		st.add(xor1)
	bool = True
	marker += flag
	print(str(c))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = set([0])
	ans = 0
	count = 0
	for i in range(n):
		count = count ^ a[i]
		if count in s:
			ans += 1
			s = set([0])
			count = 0
		s.add(count)
	print(ans)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	x = 0
	s = set()
	s.add(0)
	for i in range(n):
		x = x ^ arr[i]
		if x in s:
			s = set()
			ans += 1
			s.add(0)
			x = 0
		s.add(x)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
from collections import Counter, deque, defaultdict
import math
import heapq
ip = sys.stdin.readline
op = sys.stdout.write
t = int(ip())
res = []
for _ in range(t):
	n = int(input())
	nums = [int(x) for x in ip().split()]
	seen = set()
	val = 0
	seen.add(0)
	count = 0
	for num in nums:
		val ^= num
		if val in seen:
			count += 1
			seen.clear()
			seen.add(0)
			val = 0
		seen.add(val)
	res.append(count)
for val in res:
	op(str(val) + '\n')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	occs = set()
	occs.add(0)
	res = xorofone = 0
	for i in range(n):
		xorofone ^= arr[i]
		if xorofone in occs:
			occs.clear()
			res += 1
			occs.add(0)
			xorofone = 0
		occs.add(xorofone)
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = {}
	ans = 0
	prev = 0
	m[0] = 1
	for i in range(len(a)):
		prev = prev ^ a[i]
		if prev in m:
			prev = 0
			m.clear()
			ans += 1
		m[prev] = 1
	print(ans)


def haxorzro(A, lstart, r):
	xor = 0
	for l in range(r, lstart - 1, -1):
		xor ^= A[l]
		if not xor:
			return True
	else:
		return False

def minops(A, N):
	lstart = 0
	ops = 0
	while True:
		for r in range(lstart, N):
			if haxorzro(A, lstart, r):
				break
		else:
			break
		lstart = r + 1
		ops += 1
	return ops
T = int(input())
for i in range(T):
	N = int(input())
	A = tuple(map(int, input().split()))
	print(minops(A, N))


for _ in range(int(input())):
	size = int(input())
	array = list(map(int, input().split()))
	maps = set()
	ans = 0
	xors = 0
	for i in array:
		xors ^= i
		if xors == 0 or xors in maps:
			ans = ans + 1
			maps = set()
			xors = 0
		else:
			maps.add(xors)
	print(ans)