You are given an array A, consisting of N integers. 

Consider the following definitions:
*Prefix xor array* of an array A is defined as the array B such that B_{i} = A_{1} \oplus \ldots \oplus A_{i}, where \oplus denotes [bitwise XOR operation].  
In other words, B=[A_{1}, A_{1} \oplus A_{2}, \ldots, A_{1} \oplus A_{2} \ldots \oplus A_{N}]
The *value* of an array A is the number of *distinct* values in array B. For example, for array A=[1, 2, 3, 0], we have B=[1, 3, 0, 0]. The array B has 3 distinct values, thus, the value of array A is 3.
One right shift on the array A is a transformation that changes the array A=[A_{1}, A_{2} \ldots, A_{N}] to A^{'}=[A_{N}, A_{1}, \ldots, A_{N-1}]. 

Calculate the maximum *value* of the array A you can get, by performing any (possibly zero) number of right shifts on the array A.

------ Input Format ------ 

- The first line of input contains T - the number of test cases you need to solve.
- The first line of each test case contains one integer N - the size of the array.
- The second line of each test case contains N space-separated integers A_{1}, \ldots, A_{N} - the elements of the array A.

------ Output Format ------ 

For each test case, output on a new line the maximum value of an array A you can achieve after performing any (possibly zero) number of right shifts on the array.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤A_{i} ≤2^{60} - 1$
- Sum of $N$ over all test cases doesn't exceed $2 \cdot 10^{5}$.

------ subtasks ------ 

Subtask 1 (20 points): Sum of $N$ over all test cases doesn't exceed $2000$.
Subtask 2 (80 points): Original constraints.

----- Sample Input 1 ------ 
3
2
0 0
6
1 1 1 2 2 2
4
1 2 2 8

----- Sample Output 1 ------ 
1
4
4

----- explanation 1 ------ 
Test case $1$: Perform zero right shifts on $A=[0,0]$. Thus, $B= [0, 0\oplus0]=[0,0]$. Thus, the *value* of array $A$ is $1$.

Test case $2$: Perform two right shifts on $A = [1, 1, 1, 2, 2, 2]$. Thus, $A$ becomes $[2, 2, 1, 1, 1, 2]$. The array $B = [2, 0, 1, 0, 1, 3]$. Thus, the *value* of $A$ is $4$. It can be shown that the value of $A$ cannot exceed $4$.

Test case $3$: Perform three right shifts on $A = [1, 2, 2, 8]$. Thus, $A$ becomes $[2, 2, 8, 1]$. The array $B = [2, 2\oplus 2, 2\oplus 2\oplus 8, 2\oplus 2\oplus 8\oplus 1] = [2, 0, 8, 9]$. Thus, the *value* of $A$ is $4$. It can be shown that the value of $A$ cannot exceed $4$.

Source: codechef | Difficulty: VERY_HARD
Tags: Range queries

Bit manipulation

Amortized analysis

Mathematics


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a.append(a[i])
	r = 0
	for i in range(2 * n):
		r = r ^ a[i]
		a[i] = r
	d = {}
	for i in range(n):
		if a[i] in d:
			d[a[i]] += 1
		else:
			d[a[i]] = 1
	res = len(d)
	for i in range(n, 2 * n):
		if a[i] in d:
			d[a[i]] += 1
		else:
			d[a[i]] = 1
		d[a[i - n]] -= 1
		if d[a[i - n]] == 0:
			del d[a[i - n]]
		res = max(res, len(d))
	print(res)


from collections import defaultdict
from collections import Counter
from collections import deque
import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	prefix = [arr[0]]
	freq = defaultdict(int)
	freq[prefix[0]] += 1
	for i in range(1, n):
		prefix.append(prefix[-1] ^ arr[i])
		freq[prefix[i]] += 1
	x = prefix[-1]
	mx = ans = len(freq)
	for i in range(n):
		freq[prefix[i]] -= 1
		if not freq[prefix[i]]:
			ans -= 1
		x ^= arr[i]
		if not freq[x]:
			ans += 1
		freq[x] += 1
		mx = max(ans, mx)
	print(mx)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a == [a[0]] * n:
		if a[0] == 0:
			print(1)
		else:
			print(2)
	else:
		(xor_dict, xor, ans) = ({}, 0, 0)
		cnt = 0
		for i in range(n):
			xor = xor ^ a[i]
			try:
				xor_dict[xor] += 1
			except:
				xor_dict[xor] = 1
				cnt += 1
		(ans, total) = (max(ans, cnt), xor)
		for i in range(n - 1):
			xor = xor ^ a[i]
			try:
				xor_dict[xor] += 1
			except:
				xor_dict[xor] = 1
			if xor_dict[xor] == 1:
				cnt += 1
			pref = xor ^ total
			if xor_dict[pref] == 1:
				cnt -= 1
			xor_dict[pref] -= 1
			ans = max(ans, cnt)
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a += a
	b = [a[0]]
	for i in range(1, 2 * n):
		b.append(b[-1] ^ a[i])
	m = 0
	d = dict()
	for i in range(n):
		if b[i] not in d:
			d[b[i]] = 1
			m += 1
		else:
			d[b[i]] += 1
	if d[b[0]] == 1:
		loc = m - 1
		del d[b[0]]
	else:
		loc = m
		d[b[0]] -= 1
	k = 1
	for j in range(n, 2 * n):
		if b[j] in d:
			d[b[j]] += 1
		else:
			loc += 1
			d[b[j]] = 0
		m = max(m, loc)
		if d[b[k]] == 1:
			loc -= 1
			del d[b[k]]
		else:
			d[b[k]] -= 1
		k += 1
	print(m)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a += a
	b = []
	b.append(a[0])
	for j in range(1, 2 * n):
		b.append(b[j - 1] ^ a[j])
	mx = 0
	d = {}
	for j in range(n):
		if b[j] not in d:
			d[b[j]] = 1
			mx += 1
		else:
			d[b[j]] += 1
	if d[b[0]] == 1:
		loc = mx - 1
		del d[b[0]]
	else:
		loc = mx
		d[b[0]] -= 1
	k = 1
	for j in range(n, 2 * n):
		if b[j] in d:
			d[b[j]] += 1
		else:
			loc += 1
			d[b[j]] = 0
		mx = max(mx, loc)
		if d[b[k]] == 1:
			loc -= 1
			del d[b[k]]
		else:
			d[b[k]] -= 1
		k += 1
	print(mx)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = 0
	b = []
	d = {}
	for j in range(0, n):
		a.append(a[j])
		s = s ^ a[j]
		b.append(s)
		try:
			d[s] += 1
		except Exception:
			d[s] = 1
	for j in range(n, n + n):
		s = s ^ a[j]
		b.append(s)
	ans = set(b[:n])
	c = len(ans)
	for j in range(0, n):
		if d[b[j]] == 1:
			ans.remove(b[j])
		d[b[j]] -= 1
		try:
			d[b[n + j]] += 1
		except Exception:
			d[b[n + j]] = 1
		ans.add(b[n + j])
		c = max(len(ans), c)
	print(c)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	nums += nums
	keep = {nums[0]: 1}
	for i in range(1, 2 * n):
		nums[i] ^= nums[i - 1]
		if i < n:
			keep[nums[i]] = keep[nums[i]] + 1 if nums[i] in keep else 1
	ans = temp = len(keep)
	for i in range(n):
		if nums[i] in keep:
			keep[nums[i]] -= 1
			if not keep[nums[i]]:
				keep.pop(nums[i])
				temp -= 1
		if nums[i + n] in keep:
			keep[nums[i + n]] += 1
		else:
			keep[nums[i + n]] = 1
			temp += 1
		ans = max(ans, temp)
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	x = 0
	c = 0
	for j in range(n):
		x = x ^ a[j]
		if x in d:
			d[x] += 1
		else:
			c += 1
			d[x] = 1
	y = 0
	maxo = c
	for j in range(n):
		y = y ^ a[j]
		if y in d:
			d[y] -= 1
			if d[y] == 0:
				c -= 1
		x = x ^ a[j]
		if x not in d or d[x] == 0:
			d[x] = 1
			c += 1
		else:
			d[x] += 1
		maxo = max(maxo, c)
	print(maxo)


for tcase in range(int(input())):
	n = int(input())
	a = [0] * (2 * n)
	i = 0
	for ai in map(int, input().split()):
		a[i] = a[i + n] = ai
		i += 1
	b = [a[0]]
	for ai in a[1:]:
		b.append(b[-1] ^ ai)
	r = 0
	c = 0
	last = dict()
	while r < n:
		if b[r] not in last:
			c += 1
		last[b[r]] = r
		r += 1
	l = 0
	ans = c
	while l < n:
		if last[b[l]] == l:
			c -= 1
			del last[b[l]]
		l += 1
		if b[r] not in last:
			c += 1
		last[b[r]] = r
		r += 1
		ans = max(ans, c)
	print(ans)


import fileinput
from collections import defaultdict

def attempt1(n, aP):
	maxvals = 0
	for shift in range(n):
		vals = set()
		xorv = 0
		for i in range(n):
			xorv = xorv ^ aP[(i - shift) % n]
			vals.add(xorv)
		l = len(vals)
		if l > maxvals:
			maxvals = l
	return maxvals

def attempt2(n, aP):
	counters = defaultdict(int)
	maxvalue = 0
	currentv = 0
	curhash_ = 0
	for i in range(n):
		curhash_ = curhash_ ^ aP[i]
		counters[curhash_] += 1
		if counters[curhash_] == 1:
			currentv += 1
		lastv = curhash_
	maxvalue = currentv
	for sh in range(1, n):
		newe = aP[n - sh]
		removed = lastv
		counters[removed] -= 1
		if counters[removed] == 0:
			counters.pop(removed)
			currentv -= 1
		xounters = defaultdict(int)
		for (k, d) in counters.items():
			xounters[k ^ newe] = d
		counters = xounters
		counters[newe] += 1
		if counters[newe] == 1:
			currentv += 1
		if currentv > maxvalue:
			maxvalue = currentv
	return maxvalue

def attempt3(n, aP):
	counters = defaultdict(int)
	maxvalue = 0
	currentv = 0
	curhash_ = 0
	for i in range(n):
		curhash_ = curhash_ ^ aP[i]
		counters[curhash_] += 1
		if counters[curhash_] == 1:
			currentv += 1
		lastv = curhash_
	maxvalue = currentv
	modifier = 0
	for sh in range(1, n):
		newe = aP[n - sh]
		removed = modifier ^ lastv
		counters[removed] -= 1
		if counters[removed] == 0:
			currentv -= 1
		modifier ^= newe
		counters[modifier ^ newe] += 1
		if counters[modifier ^ newe] == 1:
			currentv += 1
		if currentv > maxvalue:
			maxvalue = currentv
	return maxvalue
with fileinput.input() as f:
	t = int(f.readline().strip())
	for i in range(t):
		n = int(f.readline().strip())
		aP = [int(e) for e in f.readline().strip().split(' ')]
		if len(aP) != n:
			raise ValueError('input length mismatch')
		mv = attempt3(n, aP)
		print(mv)


import sys
sys.setrecursionlimit(10 ** 6)
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr += arr
	temp = 0
	for i in range(2 * n):
		arr[i] = arr[i] ^ temp
		temp = arr[i]
	h = Counter(arr[:n])
	c = [len(h)]
	for i in range(0, n):
		if arr[i + n] not in h:
			h[arr[i + n]] = 0
		h[arr[i + n]] += 1
		h[arr[i]] -= 1
		if h[arr[i]] == 0:
			del h[arr[i]]
		c.append(len(h))
	print(max(c))