Guddu was participating in a programming contest. He only had one problem left when his mother called him for dinner. Guddu is well aware how angry his mother could get if he was late for dinner and he did not want to sleep on an empty stomach, so he had to leave that last problem to you. Can you solve it on his behalf?
For a given sequence of positive integers $A_1, A_2, \ldots, A_N$, you are supposed to find the number of triples $(i, j, k)$ such that $1 \le i < j \le k \le N$ and
Ai⊕Ai+1⊕…⊕Aj−1=Aj⊕Aj+1⊕…⊕Ak,Ai⊕Ai+1⊕…⊕Aj−1=Aj⊕Aj+1⊕…⊕Ak,A_i \oplus A_{i+1} \oplus \ldots \oplus A_{j-1} = A_j \oplus A_{j+1} \oplus \ldots \oplus A_k \,,
where $\oplus$ denotes bitwise XOR.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of triples.

-----Constraints-----
- $1 \le T \le 10$
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^6$ for each valid $i$

-----Subtasks-----
Subtask #1 (20 points):
- $1 \le T \le 5$
- $1 \le N \le 100$
Subtask #2 (30 points):
- $1 \le T \le 5$
- $1 \le N \le 1,000$
Subtask #3 (50 points): original constraints

-----Example Input-----
1
3
5 2 7

-----Example Output-----
2

-----Explanation-----
Example case 1: The triples are $(1, 3, 3)$, since $5 \oplus 2 = 7$, and $(1, 2, 3)$, since $5 = 2 \oplus 7$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


Solutions:
for _ in range(int(input())):
	N = int(input())
	List = [int(x) for x in input().split()]
	Prefix = []
	Temp = List[0]
	Prefix.append(List[0])
	for i in range(1, N):
		Temp = List[i] ^ Temp
		Prefix.append(Temp)
	ans = 0
	Dict = {0: list()}
	Dict[0].append(0)
	Dict[0].append(0)
	for i in range(N):
		if Prefix[i] in Dict:
			count = len(Dict[Prefix[i]]) - 1
			Dict[Prefix[i]].append(i + 1)
			ans += (i + 1) * count - count - Dict[Prefix[i]][0]
			Dict[Prefix[i]][0] += i + 1
		else:
			Dict[Prefix[i]] = list()
			Dict[Prefix[i]].append(i + 1)
			Dict[Prefix[i]].append(i + 1)
	print(ans)


from collections import defaultdict

def solve(C, N):
	cnt = defaultdict(list)
	cnt[0].append(-1)
	r = 0
	for i in range(len(C)):
		r = r ^ C[i]
		cnt[r].append(i)
	res = 0
	for l in cnt:
		x = len(cnt[l]) - 1
		neg = x
		y = 0
		for k in range(len(cnt[l]))[::-1]:
			y += x * cnt[l][k] - neg
			x -= 2
			neg -= 1
		res += y
	return res

def main():
	for _ in range(int(input())):
		N = int(input())
		C = list(map(int, input().split()))
		print(solve(C, N))
main()


from collections import defaultdict
t = int(input())
while t:
	n = int(input())
	A = list(map(int, input().split()))
	pre_xor = 0
	c = defaultdict(list)
	c[0].append(1)
	for i in range(n):
		c[pre_xor ^ A[i]].append(i + 2)
		pre_xor = pre_xor ^ A[i]
	final_ans = 0
	for (key, value) in c.items():
		sum_key = 0
		current_len = len(value)
		for i in range(1, current_len):
			sum_key += i * (current_len - i) * (value[i] - value[i - 1] - 1)
			sum_key += i * (i - 1) // 2
		final_ans += sum_key
	print(final_ans)
	t -= 1


import collections

def oprsn(l):
	n = len(l)
	s = sum(l)
	ans = 0
	for v in l:
		s -= v
		n -= 1
		ans += s - n * v - n
	return ans
for _ in range(int(input())):
	(n, a) = (int(input()), list(map(int, input().split())))
	x = ans = 0
	p = [0]
	d = collections.defaultdict(list)
	for v in a:
		x = x ^ v
		p += [x]
	for i in range(n + 1):
		d[p[i]] += [i]
	for k in d:
		ans += oprsn(d[k])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	prefix_xor = [arr[0]]
	for i in range(1, len(arr)):
		prefix_xor.append(prefix_xor[-1] ^ arr[i])
	xor_map = {0: [1, 0]}
	total_triplets = 0
	for (index, elem) in enumerate(prefix_xor):
		if elem not in xor_map:
			xor_map[elem] = [1, index + 1]
		else:
			(cnt, sum_all_pos) = (xor_map[elem][0], xor_map[elem][1])
			total_triplets += cnt * (index + 1) - cnt - sum_all_pos
			xor_map[elem][0] += 1
			xor_map[elem][1] += index + 1
	print(total_triplets)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	pxor = [0]
	for i in range(n):
		pxor += [arr[i] ^ pxor[i]]
	d = dict()
	for i in range(n + 1):
		if pxor[i] in d.keys():
			d[pxor[i]][2] = (i - d[pxor[i]][1]) * d[pxor[i]][0] + d[pxor[i]][2]
			d[pxor[i]][1] = i
			d[pxor[i]][3] += d[pxor[i]][2] - d[pxor[i]][0]
			d[pxor[i]][0] += 1
		else:
			d[pxor[i]] = [1, i, 0, 0]
	sums = 0
	for i in d.values():
		sums += i[3]
	print(sums)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = tuple(map(int, input().split()))
	prefix = [0]
	for item in a:
		temp = prefix[-1] ^ item
		prefix.append(temp)
	m = {}
	m[0] = (1, 0)
	ans = 0
	for i in range(1, len(prefix)):
		try:
			ans += m[prefix[i]][0] * i - m[prefix[i]][1] - m[prefix[i]][0]
			m[prefix[i]] = (m[prefix[i]][0] + 1, m[prefix[i]][1] + i)
		except:
			m[prefix[i]] = (1, i)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	xorArr = [0 for _ in range(n)]
	xorArr[0] = l[0]
	for i in range(1, n):
		xorArr[i] = xorArr[i - 1] ^ l[i]
	vec = []
	dic = {}
	count = 0
	dic[0] = [-1]
	for i in range(n):
		if dic.get(xorArr[i]):
			dic.get(xorArr[i]).append(i)
		else:
			a = []
			a.append(i)
			dic[xorArr[i]] = a
	for i in dic:
		l = dic[i]
		leng = len(l)
		for j in range(leng):
			count += j * l[j] - (leng - j - 1) * l[j]
		count -= leng * (leng - 1) // 2
	print(count)


import itertools

def findsubsets(s, n):
	return tuple(itertools.combinations(s, n))

def xorfunc(low, hi, a):
	xor1 = 0
	for i in range(low, hi + 1):
		xor1 ^= a[i]
	if xor1 == 0:
		return hi - low
	else:
		return 0
t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	a = a.split()
	a = [int(it) for it in a]
	xor = 0
	xorsum = []
	for i in a:
		xor ^= i
		xorsum.append(xor)
	interlist = [i for i in range(n)]
	interlist2 = findsubsets(interlist, 2)
	interlist2 = [xorfunc(i, j, a) for (i, j) in interlist2]
	print(sum(interlist2))


def sumPairs(arr, n):
	sum = 0
	for i in range(n - 1, -1, -1):
		sum += i * arr[i] - (n - 1 - i) * arr[i]
	return sum - n * (n - 1) // 2
R = lambda : map(int, input().split())
t = int(input())
for _ in range(t):
	n = int(input())
	xs = list(map(int, input().split()))
	xor = 0
	dict = {0: [0]}
	count = 0
	i = 0
	for x in xs:
		xor = xor ^ x
		if xor not in dict:
			dict[xor] = [i + 1]
		else:
			dict[xor].append(i + 1)
		i += 1
	ans = 0
	for i in dict.values():
		if len(i) == 1:
			continue
		else:
			ans += sumPairs(i, len(i))
	print(ans)


t = int(input())
for _ in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	res = 0
	prefix_xor = []
	temp = 0
	prefix_xor.append(0)
	for i in range(N):
		temp = temp ^ A[i]
		prefix_xor.append(temp)
	prefix_dict = dict()
	for i in range(len(prefix_xor)):
		prefix_dict[prefix_xor[i]] = []
	for i in range(len(prefix_xor)):
		prefix_dict[prefix_xor[i]].append(i)
	for (key, value) in prefix_dict.items():
		if len(value) == 1:
			pass
		else:
			l = len(value)
			for i in range(l - 1):
				res += (value[i + 1] - value[i]) * (i + 1) * (l - i - 1)
				res -= l - i - 1
	print(res)


for testcase in range(int(input())):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	sum = [0] * 2000020
	cnt = [0] * 2000020
	s = 0
	ans = 0
	cnt[0] = 1
	sum[0] = 1
	for i in range(1, len(a)):
		s ^= a[i]
		ans += i * cnt[s] - sum[s]
		cnt[s] += 1
		sum[s] += i + 1
	print(ans)


import math
from collections import defaultdict
t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	tmp = 0
	tmp2 = 0
	index = 0
	j = 0
	t = [int(0) for _ in range(n)]
	pl = 0
	s = set()
	l = []
	h = dict()
	(rows, cols) = (10, 10)
	for i in range(n):
		if i == 0:
			t[i] = a[i]
			s.add(t[i])
		else:
			t[i] = a[i] ^ t[i - 1]
			s.add(t[i])
			if t[i] == 0:
				cnt += i
		h.setdefault(t[i], []).append(i)
	for j in h:
		ind = h[j]
		length = len(ind)
		for i in range(length):
			cnt += i * ind[i] - (length - i - 1) * ind[i]
		cnt -= length * (length - 1) // 2
	print(cnt)


def find_coeffs(n):
	coeffs = [0 for _ in range(n)]
	for i in range(1, n + 1):
		coeffs[i - 1] = i + (n - i) * i
	return coeffs

def find_diff(indices):
	diff = [0 for _ in range(len(indices) - 1)]
	for i in range(1, len(indices)):
		diff[i - 1] = int(indices[i] - indices[i - 1])
	return diff
test_cases = int(input())
for test in range(test_cases):
	n = int(input())
	seq = list(map(int, input().split()))
	triplets = 0
	res = [0 for _ in range(n + 1)]
	for i in range(1, n + 1):
		res[i] = res[i - 1] ^ seq[i - 1]
	xors = {}
	for i in range(n + 1):
		if res[i] not in xors:
			xors[res[i]] = [i]
		else:
			xors[res[i]].append(i)
	for key in xors.keys():
		if len(xors[key]) > 1:
			diff_array = find_diff(xors[key])
			l = len(diff_array)
			coeffs = find_coeffs(l)
			triplets += sum([diff_array[i] * coeffs[i] for i in range(l)]) - int(l * (l + 1) / 2)
	print(triplets)


def maker_dictttt(a):
	ind = {}
	for i in range(len(a)):
		try:
			if ind[a[i]]:
				ind[a[i]].append(i)
		except KeyError:
			ind[a[i]] = [i]
	return ind

def nC2(n):
	return int(n * (n - 1) / 2)

def ardderr(arr):
	rest = 0
	n = len(arr)
	prefix = -(n - 1)
	for i in arr:
		rest = rest + prefix * i
		prefix = prefix + 2
	return int(rest - nC2(n))
for t in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	a = []
	xor = 0
	for i in x:
		xor ^= i
		a.append(xor)
	ans = 0
	rest = maker_dictttt(a)
	for j in rest.keys():
		if j == 0:
			ans = ans + ardderr(rest[j])
			ans = ans + sum(rest[j])
		else:
			ans = ans + ardderr(rest[j])
	print(ans)


def passwr(length, guddu):
	password = 0
	values = {}
	compute = guddu[0]
	values[compute] = [1, 1]
	j = 1
	while j != length:
		compute = compute ^ guddu[j]
		try:
			if not compute:
				password += j
			password += values[compute][1] * j - values[compute][0]
			values[compute] = [values[compute][0] + (j + 1), values[compute][1] + 1]
		except:
			values[compute] = [j + 1, 1]
		j += 1
	return password
test = int(input())
for i in range(test):
	length = int(input())
	guddu = [int(k) for k in input().split()]
	print(passwr(length, guddu))


def reverse_indexed_map(myList):
	map_of_values = {}
	for (index, val) in enumerate(myList):
		if val not in map_of_values.keys():
			map_of_values[val] = [index]
		else:
			map_of_values[val] += [index]
	return map_of_values

def number_of_triplets(indexed_values):
	num = 0
	if 0 in indexed_values.keys():
		indexed_values[0] += [-1]
	for (key, indices_list) in indexed_values.items():
		indices_list.sort(reverse=True)
		length = len(indices_list) - 1
		l = len(indices_list)
		for i in indices_list:
			num += length * i
			length -= 2
		num -= int(l * (l - 1) / 2)
	return num
for i in range(0, int(input())):
	n = int(input())
	input_list = [int(x) for x in input().split()]
	for (index, val) in enumerate(input_list):
		if index == 0:
			continue
		else:
			input_list[index] = input_list[index - 1] ^ val
	temp = reverse_indexed_map(input_list)
	answer = number_of_triplets(temp)
	print(answer)


def xor(arr, n):
	result = 0
	arrxor = [0 for _ in range(n)]
	arrxor[0] = arr[0]
	i = 1
	while i < n:
		arrxor[i] = arrxor[i - 1] ^ arr[i]
		i += 1
	mydict = {}
	mydict[0] = [-1]
	for (ind, elem) in enumerate(arrxor):
		if elem in mydict:
			mydict[elem].append(ind)
		else:
			mydict.update({elem: [ind]})
	for (key, value) in mydict.items():
		if len(value) > 1:
			k = len(value) - 1
			x = 0
			i = k
			while i > 0:
				result += k * mydict[key][i] - k * mydict[key][x]
				x += 1
				k -= 1
				i -= 1
			result -= int(len(value) * (len(value) - 1) / (2 * 1))
	return result
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	print(xor(a, n))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	xor = []
	xor.append(arr[0])
	for i in range(1, n):
		xor.append(xor[i - 1] ^ arr[i])
	di = {}
	for i in range(n):
		if xor[i] not in di:
			di[xor[i]] = []
		di[xor[i]].append(i)
	cnt = 0
	for i in di:
		arr = di[i]
		su = 0
		if i == 0:
			su += sum(arr)
		if len(arr) == 2:
			su += arr[1] - arr[0] - 1
		if len(arr) > 2:
			n1 = len(arr)
			j = n1 - 1
			suo = 0
			suo -= int(j * (j + 1) / 2)
			if n1 % 2 == 0:
				j = n1 + 1
				for k in range(int(n1 / 2)):
					j -= 2
					suo -= j * arr[k]
				for k in range(int(n1 / 2), n1):
					suo += j * arr[k]
					j += 2
			else:
				for k in range(int(n1 / 2)):
					suo -= j * arr[k]
					j -= 2
				j = 0
				for k in range(int(n1 / 2), n1):
					suo += j * arr[k]
					j += 2
			su += suo
		cnt += su
	print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	my_arr = list()
	my_list = list()
	res = 0
	my_arr = [0] * 1000000
	my_list = [0] * 1000000
	arr2 = list(range(1000001))
	my_arr[x[0]] = 0
	my_list[x[0]] += 1
	prev1 = 0
	xr = 0
	pos = 0
	for i in range(1, n):
		xr = x[i] ^ xr
		prev2 = 0
		pos = 0
		pos = arr2[xr]
		prev2 = prev1
		res += i * my_list[pos] - my_arr[pos]
		my_arr[prev2] += i
		my_list[prev2] += 1
		prev1 = pos
	print(res)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	dp = [a[0]]
	cnt = 0
	(value, rang) = (dict(), dict())
	value[dp[0]] = 0
	rang[dp[0]] = 0
	for i in range(1, n):
		dp.append(dp[i - 1] ^ a[i])
		value[dp[i]] = 0
		rang[dp[i]] = 0
	for i in range(n):
		if value[dp[i]] > 0:
			if dp[i] == 0:
				cnt += i
				cnt += (i - 1) * value[dp[i]] - rang[dp[i]]
				value[dp[i]] += 1
				rang[dp[i]] += i
			else:
				cnt += (i - 1) * value[dp[i]] - rang[dp[i]]
				value[dp[i]] += 1
				rang[dp[i]] += i
		else:
			if dp[i] == 0:
				cnt += i
			value[dp[i]] += 1
			rang[dp[i]] += i
	print(cnt)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	fin = 0
	for j in range(n):
		l1.append(0)
	d1 = {}
	d2 = {}
	d3 = {}
	d4 = {}
	d5 = {}
	d6 = {}
	l1[0] = l[0]
	for j in range(1, n):
		l1[j] = l1[j - 1] ^ l[j]
	d1[0] = [0]
	d2[0] = d3[0] = d4[0] = 0
	d5[0] = []
	for j in range(n):
		temp = 0 ^ l1[j]
		if l1[j] in d1.keys():
			d1[l1[j]].append(j + 1 - d2[l1[j]])
		else:
			d1[l1[j]] = [0]
			d2[l1[j]] = j + 1
		if l1[j] not in d5.keys():
			d5[l1[j]] = []
			d3[l1[j]] = 0
			d4[l1[j]] = 0
		else:
			d5[l1[j]].append(d1[l1[j]][-1] - d1[l1[j]][-2])
			d3[l1[j]] += 1
			d4[l1[j]] += d5[l1[j]][-1] * d3[l1[j]]
		if temp in d6.keys():
			if l1[j] == 0:
				fin += d4[l1[j]] - d6[temp] - d5[l1[j]][-1]
			else:
				fin += d4[l1[j]] - d6[temp]
		if l1[j] == 0:
			fin += d5[l1[j]][-1] - 1
		d6[l1[j]] = d6.get(l1[j], 0) + 1
	print(fin)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	ans = 0
	a = [0] * 1000000
	b = [0] * 1000000
	m = [0] * 1000000
	j = 0
	a[0] = 1
	m[0] = -1
	for i in range(n):
		s = 0
		j = j ^ A[i]
		if a[j]:
			s = i - m[j]
			b[j] = b[j] + (a[j] * s - 1)
			ans += b[j]
		m[j] = i
		a[j] += 1
	print(ans)


test_cases = int(input())
for test in range(test_cases):
	n = int(input())
	seq = list(map(int, input().split()))
	triplets = 0
	res = [0 for _ in range(n)]
	for i in range(n - 1):
		res[i] = seq[i]
		for j in range(i + 1, n):
			res[j] = res[j - 1] ^ seq[j]
			if res[j] == 0:
				triplets += j - i
	print(triplets)


t = int(input())
for _ in range(t):
	size = int(input())
	given = [0]
	[given.append(int(i)) for i in str(input()).split(' ')]
	s = 0
	ans = 0
	count = [0] * (10 ** 6 + 1)
	sum = [0] * (10 ** 6 + 1)
	for (index, element) in enumerate(given):
		s ^= element
		ans += count[s] * index - sum[s]
		count[s] += 1
		sum[s] += index + 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = [0]
	p = [[0, 0]]
	prev = 0
	ans = 0
	counter = 0
	for i in range(1, n + 1):
		x.append(x[i - 1] ^ l[i - 1])
		p.append([x[i], i])
	p = sorted(p)
	for i in range(1, len(p)):
		if p[i][0] == p[i - 1][0]:
			counter += 1
		else:
			counter = 0
			prev = 0
			continue
		prev = prev + (p[i][1] - p[i - 1][1] - 1) * counter + counter - 1
		ans += prev
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 0
	count = 0
	for i in range(0, n):
		sum = a[i]
		for j in range(i + 1, n):
			sum = sum ^ a[j]
			if sum == 0:
				count = count + (j - i)
	print(count)


def count_subarrays(l):
	res = 0
	p = []
	p.append(0)
	for i in range(1, len(l)):
		p.append(p[i - 1] + l[i - 1])
	for i in range(1, len(l)):
		res += i * l[i] - p[i] - i
	return res

def special_case(l):
	res = 0
	for i in l:
		res += i
	return res

def solve():
	arr = []
	pref = []
	dic = {}
	counter = 0
	n = int(input())
	arr = [int(x) for x in input().split()]
	pref.append(arr[0])
	dic.update({pref[0]: []})
	dic[pref[0]].append(0)
	for i in range(1, n):
		pref.append(arr[i] ^ pref[i - 1])
		if pref[i] not in dic.keys():
			dic.update({pref[i]: []})
		dic[pref[i]].append(i)
	for i in dic:
		if i == 0:
			counter += special_case(dic[i])
		if len(dic[i]) > 1:
			counter += count_subarrays(dic[i])
	print(counter)

def main():
	t = int(input())
	while t:
		t -= 1
		solve()
main()


test_cases = int(input())
for test in range(test_cases):
	n = int(input())
	seq = list(map(int, input().split()))
	triplets = 0
	res = [0 for _ in range(n + 1)]
	for i in range(1, n + 1):
		res[i] = res[i - 1] ^ seq[i - 1]
	xors = {}
	for i in range(n + 1):
		if res[i] not in xors:
			xors[res[i]] = [i]
		else:
			xors[res[i]].append(i)
	for key in xors.keys():
		if len(xors[key]) > 1:
			for i in range(len(xors[key]) - 1):
				for j in range(i + 1, len(xors[key])):
					triplets += int(xors[key][j] - xors[key][i] - 1)
	print(triplets)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	xor = [0] * n
	xor[0] = a[0]
	m = a[0]
	for i in range(1, n):
		xor[i] = xor[i - 1] ^ a[i]
		m = max(m, xor[i])
	v = []
	ans = 0
	sum = [0] * (m + 1)
	for j in range(m + 2):
		v.append([])
	for i in range(n):
		if xor[i] == 0:
			ans += i
		j = xor[i]
		size = len(v[j])
		ans += size * i - sum[j] - size
		v[j].append(i)
		sum[j] += i
	print(ans)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	pxor = [0]
	for i in range(n):
		pxor += [arr[i] ^ pxor[i]]
	m = max(pxor)
	count = [0] * (m + 1)
	ind = [-1] * (m + 1)
	val = [0] * (m + 1)
	res = [0] * (m + 1)
	for i in range(n + 1):
		val[pxor[i]] += (i - ind[pxor[i]]) * count[pxor[i]]
		if val[pxor[i]]:
			res[pxor[i]] += val[pxor[i]] - count[pxor[i]]
		ind[pxor[i]] = i
		count[pxor[i]] += 1
	sums = 0
	for i in res:
		sums += i
	print(sums)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	m = [0] * n
	for i in range(n):
		if i == 0:
			m[i] = l[i]
		else:
			m[i] = m[i - 1] ^ l[i]
	d = {}
	c = 0
	for i in l:
		c = c ^ i
	for i in range(n - 1, -1, -1):
		try:
			x = d[l[i] ^ c]
			ans += x[0] - x[1] * i
		except:
			pass
		try:
			d[m[i]] = [d[m[i]][0] + i, d[m[i]][1] + 1]
		except:
			d[m[i]] = [i, 1]
		c = c ^ l[i]
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	inp = [int(i) for i in input().split()]
	t = t - 1
	xorarr = [0] * n
	xorarr[0] = inp[0]
	mydict = dict()
	mydict[xorarr[0]] = 1
	for i in range(1, n):
		xorarr[i] = xorarr[i - 1] ^ inp[i]
		if xorarr[i] not in mydict:
			mydict[xorarr[i]] = 1
		else:
			mydict[xorarr[i]] = mydict[xorarr[i]] + 1
	mydicts = dict()
	sums = 0
	for i in range(n):
		if xorarr[i] == 0:
			sums = sums + i
		if xorarr[i] not in mydicts:
			val = 0 - i * (mydict[xorarr[i]] - 1)
			mydicts[xorarr[i]] = [1, val]
		else:
			val = (2 * mydicts[xorarr[i]][0] - mydict[xorarr[i]] + 1) * i
			mydicts[xorarr[i]][0] += 1
			mydicts[xorarr[i]][1] += val
	for i in list(mydicts.keys()):
		sums = sums + mydicts[i][1] - mydict[i] * (mydict[i] - 1) / 2
	print(int(sums))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	s = set()
	for i in range(0, n - 1):
		for k in range(1, n):
			x = 0
			for y in a[i:k + 1]:
				x ^= y
			if x == 0:
				for j in range(i + 1, k + 1):
					if (i, j, k) not in s:
						s.add((i, j, k))
						c += 1
	print(c)


def xorContest(seq):
	ans = 0
	count = {}
	bad_count = {}
	pre_xor = [None] * (len(seq) + 1)
	pre_xor[0] = 0
	for i in range(1, len(seq) + 1):
		pre_xor[i] = pre_xor[i - 1] ^ seq[i - 1]
	for i in range(len(pre_xor)):
		xor = pre_xor[i]
		ans = ans + i * (count[xor] if xor in count else 0) - (bad_count[xor] if xor in bad_count else 0)
		if xor in count:
			count[xor] = count[xor] + 1
			bad_count[xor] = bad_count[xor] + (i + 1)
		else:
			count[xor] = 1
			bad_count[xor] = i + 1
	return ans
X = [None] * 100000
R = [None] * 100000
T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	print(xorContest(A))


def tppp(ivvv):
	nmmm = 0
	if 0 in ivvv.keys():
		ivvv[0] += [-1]
	for (key, indlll) in ivvv.items():
		indlll.sort(reverse=True)
		length = len(indlll) - 1
		l = len(indlll)
		for i in indlll:
			nmmm += length * i
			length -= 2
		nmmm = nmmm - int(l * (l - 1) / 2)
	return nmmm

def rvv(mllll):
	map_of_values = {}
	for (index, val) in enumerate(mllll):
		if val not in map_of_values.keys():
			map_of_values[val] = [index]
		else:
			map_of_values[val] += [index]
	return map_of_values
try:
	tttt = int(input())
except:
	quit()
while tttt != 0:
	number_of_integers = int(input())
	illll = [int(x) for x in input().split()]
	for (index, val) in enumerate(illll):
		if index == 0:
			continue
		else:
			illll[index] = illll[index - 1] ^ val
	tmpppp = rvv(illll)
	anss = tppp(tmpppp)
	print(anss)
	tttt -= 1


final_result = []

def get_no_of_triplets(array):
	result = 0
	aux_array = array
	length = len(array)
	hash_table = {}
	for i in range(1, length):
		aux_array[i] = aux_array[i] ^ aux_array[i - 1]
	for i in range(length):
		if aux_array[i] in hash_table:
			hash_table[aux_array[i]].append(i)
		else:
			hash_table[aux_array[i]] = [i]
	for key in list(hash_table.keys()):
		temp_array = hash_table[key]
		sum = 0
		l = len(temp_array)
		if l > 1:
			for i in range(0, l):
				sum += temp_array[i] * (l - 1 - 2 * i) * -1
				if key == 0:
					sum += temp_array[i]
			sum -= l * (l - 1) / 2
		elif key == 0:
			sum += temp_array[0]
		result += sum
	return int(result)
for _ in range(int(input())):
	input()
	ip = input().split(' ')
	final_result.append(get_no_of_triplets([int(i) for i in ip]))
for i in range(len(final_result)):
	print(final_result[i])


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	pXor = [0]
	for i in A:
		pXor.append(i ^ pXor[-1])
	xors = defaultdict(int)
	counts = defaultdict(int)
	ans = 0
	for (ind, i) in enumerate(pXor):
		ans += ind * counts[i] - xors[i]
		xors[i] += ind + 1
		counts[i] += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().rstrip().split()))
	xlst = [0 for j in range(n)]
	xlst[0] = lst[0]
	for j in range(1, n):
		xlst[j] = xlst[j - 1] ^ lst[j]
	xlst.insert(0, 0)
	di = {}
	for j in xlst:
		di[j] = []
	for j in range(n + 1):
		tem = xlst[j]
		di[tem].append(j)
	num = 0
	for ind in di:
		j = di[ind]
		te = len(j)
		if te < 2:
			continue
		su = sum(j) + te
		way = 0
		sta = -1
		for k in range(te - 1):
			f1 = j[k] - sta
			tem = f1 * (te - k)
			su = su - tem
			way += su - (te - k - 1)
			sta = j[k]
		num = num + way
	an = num
	print(an)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	xor = [0] * n
	xor[0] = a[0]
	bad = defaultdict(int)
	cnt = defaultdict(int)
	ans = 0
	for i in range(1, n):
		xor[i] = xor[i - 1] ^ a[i]
		if xor[i] == 0:
			ans += i
	for i in range(n):
		if xor[i] in bad:
			ans += i * cnt[xor[i]] - bad[xor[i]]
		bad[xor[i]] += i + 1
		cnt[xor[i]] += 1
	print(ans)


def reverseindex(ll):
	V = {}
	for (ind, v) in enumerate(ll):
		if v not in V.keys():
			V[v] = [ind]
		else:
			V[v] += [ind]
	return V

def trimp(iv):
	num = 0
	if 0 in iv.keys():
		iv[0] += [-1]
	for (k, il) in iv.items():
		il.sort(reverse=True)
		length = len(il) - 1
		l = len(il)
		for i in il:
			num += length * i
			length -= 2
		num -= int(l * (l - 1) / 2)
	return num
try:
	t = int(input())
except:
	quit()
while t != 0:
	n = int(input())
	l = [int(y) for y in input().split()]
	for (ind, v) in enumerate(l):
		if ind == 0:
			continue
		else:
			l[ind] = l[ind - 1] ^ v
	temp = reverseindex(l)
	r = trimp(temp)
	print(r)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	pair = {}
	pair[0] = [-1]
	pair[a[0]] = [0]
	for i in range(1, n):
		a[i] = a[i - 1] ^ a[i]
		if a[i] in pair:
			pair[a[i]].append(i)
		else:
			pair[a[i]] = [i]
	ans = 0
	for lst in pair.values():
		x = []
		for i in range(1, len(lst)):
			x.append(lst[i] - lst[i - 1])
		m = len(x)
		l = m
		k = 1
		while k <= l:
			ans += m * k * x[k - 1]
			k += 1
			m -= 1
		ans -= l * (l + 1) // 2
	print(ans)


def prefix(lis):
	pre = [lis[0]]
	for i in range(1, len(lis)):
		pre.append(pre[i - 1] + lis[i])
	sum = 0
	for i in range(1, len(lis)):
		sum = sum + (i * lis[i] - pre[i - 1] - i)
	return sum
t = int(input())
for q in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	di = {}
	xor = 0
	for i in range(n):
		xor = xor ^ arr[i]
		if di.__contains__(xor) == False:
			di[xor] = [i]
		else:
			lis = di[xor]
			lis.append(i)
			di[xor] = lis
			lis = []
	res = list(di.values())
	ans = 0
	if di.__contains__(0):
		ans += sum(list(di[0]))
	for i in range(len(res)):
		ans += prefix(res[i])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		x = 0
		for j in range(i + 1, n):
			x ^= l[j]
			if x == l[i]:
				ans += j - i
	print(ans)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	prefix = [0] * n
	prefix[0] = arr[0]
	for i in range(1, n):
		prefix[i] = arr[i] ^ prefix[i - 1]
	pos = {0: [0]}
	for i in range(n):
		if prefix[i] not in pos:
			pos[prefix[i]] = [i + 1]
		else:
			pos[prefix[i]].append(i + 1)
	result = 0
	for (key, value) in pos.items():
		size = len(value)
		cum = [0] * size
		cum[0] = value[0]
		temp = 0
		for i in range(1, size):
			cum[i] = cum[i - 1] + value[i]
			temp += value[i] * i - cum[i - 1]
		temp -= size * (size - 1) // 2
		result += temp
	print(result)
	t -= 1


t = int(input())
for _ in range(t):
	q = 0
	n = int(input())
	a = list(map(int, input().split()))
	x = []
	x.append(0)
	for i in range(n):
		x.append(x[i] ^ a[i])
	p = dict()
	for i in range(n + 1):
		p[x[i]] = []
	for i in range(n + 1):
		p[x[i]].append(i)
	for (k, v) in p.items():
		if len(v) != 1:
			for i in range(len(v) - 1, -1, -1):
				q += i * (v[i] - 1) - (len(v) - i - 1) * v[i]
	print(q)


for t in range(int(input())):
	n = int(input())
	l = [int(j) for j in input().split()]
	d = {0: [1, 0]}
	v = 0
	count = 0
	for i in range(n):
		v = v ^ l[i]
		if v in d:
			count = count + i * d[v][0] - d[v][1]
			d[v][0] += 1
			d[v][1] += i + 1
		else:
			d[v] = [1, i + 1]
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	xor = [0]
	for i in range(n):
		last = xor[-1]
		xor.append(last ^ arr[i])
	d = {}
	for i in range(len(xor)):
		if xor[i] not in d:
			d[xor[i]] = [i]
		else:
			d[xor[i]].append(i)
	ans = 0
	for i in d:
		temp = d[i]
		temp1 = sum(temp)
		terms = len(temp) - 1
		for j in range(len(temp)):
			cur = temp[j]
			temp1 = temp1 - cur
			ans += temp1 - terms * cur - terms
			terms -= 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	XOR = 0
	d = {}
	res = 0
	d[0] = [0, 1]
	for i in range(len(l)):
		XOR ^= l[i]
		if XOR in d:
			res += d[XOR][1] * i - d[XOR][0]
			d[XOR][0] += i + 1
			d[XOR][1] += 1
		else:
			d[XOR] = [i + 1, 1]
	print(res)


def rev_index(myList):
	V = {}
	for (index, val) in enumerate(myList):
		if val not in V.keys():
			V[val] = [index]
		else:
			V[val] += [index]
	return V

def No_tri(IV):
	num = 0
	if 0 in IV.keys():
		IV[0] += [-1]
	for (key, IL) in IV.items():
		IL.sort(reverse=True)
		length = len(IL) - 1
		l = len(IL)
		for i in IL:
			num += length * i
			length -= 2
		num -= int(l * (l - 1) / 2)
	return num
try:
	T = int(input())
except:
	quit()
while T != 0:
	N = int(input())
	L = [int(x) for x in input().split()]
	for (index, val) in enumerate(L):
		if index == 0:
			continue
		else:
			L[index] = L[index - 1] ^ val
	temp = rev_index(L)
	res = No_tri(temp)
	print(res)
	T -= 1


import random, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right

def solution(li):
	ma = {}
	st = {}
	ma[0] = 1
	st[0] = 1
	s = 0
	c = 0
	for i in range(len(li)):
		s ^= li[i]
		c += ma.get(s, 0) * (i + 1) - st.get(s, 0)
		ma[s] = ma.get(s, 0) + 1
		st[s] = st.get(s, 0) + i + 2
	return c

def input_test():
	for _ in range(int(input())):
		n = int(input())
		li = list(map(int, input().strip().split(' ')))
		out = solution(li)
		print(out)

def test():
	pass
input_test()


from bisect import bisect_left, bisect_right
from math import sqrt, ceil, floor, factorial
from heapq import heapify, heappush, heappop, heappushpop, heapreplace, merge, nlargest, nsmallest
from collections import Counter, deque, defaultdict, OrderedDict, namedtuple
mod = 10 ** 9 + 7
inf = float('inf')
negin = float('-inf')
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	xor = 0
	preXor = dict()
	preXor[0] = [0]
	for item in range(n):
		xor ^= a[item]
		if xor in preXor:
			preXor[xor].append(item + 1)
		else:
			preXor[xor] = [item + 1]
	for x in preXor:
		l = len(preXor[x])
		if l >= 2:
			for pos in range(l):
				ans += pos * preXor[x][pos] - (l - 1 - pos) * preXor[x][pos]
			ans -= l * (l - 1) // 2
	print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	a = list()
	x1 = b[0]
	a.append(0)
	a.append(b[0])
	for i in range(1, n):
		x1 ^= b[i]
		a.append(x1)
	c = {}
	for i in range(len(a)):
		c.setdefault(a[i], []).append(i)
	(x, x3) = (0, 0)
	for i in c:
		x1 = 1
		x2 = 1
		if len(c[i]) > 1:
			for j in range(1, len(c[i])):
				x += (c[i][j] - 1 - c[i][0]) * x1
				x1 += 1
			for k in range(len(c[i]) - 2, 0, -1):
				x3 += (c[i][k] - c[i][0]) * x2
				x2 += 1
	print(x - x3)


for _ in range(int(input())):
	n = int(input()) + 1
	a = [0] + list(map(int, input().split()))
	for i in range(1, n):
		a[i] ^= a[i - 1]
	r = {}
	ans = 0
	r[0] = (1, 0)
	for i in range(1, n):
		(cnt, sm) = r.get(a[i], (0, 0))
		ans += cnt * (i - 1) - sm
		r[a[i]] = (cnt + 1, sm + i)
	print(ans)


from collections import defaultdict

def solve(C, N):
	ar = [(0, -1)]
	cnt = defaultdict(list)
	cnt[0].append(-1)
	r = 0
	for i in range(len(C)):
		r = r ^ C[i]
		cnt[r].append(i)
	res = 0
	for l in cnt:
		for k in range(len(cnt[l]) - 1):
			for j in range(k + 1, len(cnt[l])):
				res += abs(cnt[l][k] - cnt[l][j]) - 1
	return res

def main():
	for _ in range(int(input())):
		N = int(input())
		C = list(map(int, input().split()))
		print(solve(C, N))
main()


import math
for _ in range(int(input())):
	N = int(input())
	Arr = [int(x) for x in input().split()]
	res = 0
	xor_array = [0] * 1000000
	length = [0] * 1000000
	x = [0] * 1000000
	xor_val = 0
	xor_array[0] = 1
	x[0] = -1
	for i in range(N):
		cnt = 0
		xor_val = xor_val ^ Arr[i]
		if xor_array[xor_val]:
			cnt = i - x[xor_val]
			length[xor_val] = length[xor_val] + (xor_array[xor_val] * cnt - 1)
			res += length[xor_val]
		x[xor_val] = i
		xor_array[xor_val] += 1
	print(res)


import itertools
from collections import defaultdict as dfd

def sumPairs(arr, n):
	s = 0
	for i in range(n - 1, -1, -1):
		s += i * arr[i] - (n - 1 - i) * arr[i]
	return s

def subarrayXor(arr, n, m):
	ans = 0
	xorArr = [0 for _ in range(n)]
	mp = dfd(list)
	xorArr[0] = arr[0]
	for i in range(1, n):
		xorArr[i] = xorArr[i - 1] ^ arr[i]
	for i in range(n):
		mp[xorArr[i]].append(i)
	a = sorted(mp.items())
	for i in a:
		diffs = 0
		if i[0] != 0:
			l = len(i[1]) - 1
			ans += sumPairs(i[1], len(i[1])) - l * (l + 1) // 2
		else:
			l = len(i[1]) - 1
			ans += sumPairs(i[1], len(i[1])) - l * (l + 1) // 2
			ans += sum(i[1])
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(subarrayXor(arr, len(arr), 0))


val = 1000000
t = int(input())
while t > 0:
	n = int(input())
	tempo = list(map(int, input().split()))
	first = list()
	second = list()
	ans = 0
	a = tempo[0]
	first = [0] * val
	second = [0] * val
	third = list(range(val + 1))
	first[tempo[0]] = 0
	second[tempo[0]] += 1
	w = 0
	q = 0
	loc = 0
	for i in range(1, n):
		q = tempo[i] ^ q
		e = 0
		loc = 0
		loc = third[q]
		e = w
		ans += i * second[loc] - first[loc]
		first[e] += i
		second[e] += 1
		w = loc
	print(ans)
	t = t - 1


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	l = []
	l = [int(x) for x in input().split()]
	prefix = []
	prefix.append(l[0])
	xor_vals = {}
	i_s = {}
	ans = 0
	for i in range(1, n):
		prefix.append(prefix[i - 1] ^ l[i])
	for i in range(0, n):
		if prefix[i] == 0:
			ans += i
		if prefix[i] not in xor_vals:
			xor_vals[prefix[i]] = 1
			i_s[prefix[i]] = i + 1
		else:
			ans += i * xor_vals[prefix[i]] - i_s[prefix[i]]
			xor_vals[prefix[i]] += 1
			i_s[prefix[i]] += i + 1
	print(ans)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	arr = list(map(int, input().split()))
	mydict = {}
	x = [0] * (n + 1)
	y = 0
	for i in range(len(arr)):
		x[i + 1] = y ^ arr[i]
		y = x[i + 1]
	for i in range(len(x)):
		if x[i] in mydict:
			mydict[x[i]].append(i)
		else:
			mydict[x[i]] = [i]
	ans = 0
	for i in mydict:
		temp = mydict[i]
		temp1 = sum(temp)
		terms = len(temp) - 1
		for j in range(len(temp)):
			cur = temp[j]
			temp1 = temp1 - cur
			ans += temp1 - terms * cur - terms
			terms -= 1
	print(ans)


for t in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	sol = 0
	(p_s, c_s) = (li[0], 0)
	tmp = dict()
	tmp[p_s] = [0, 1]
	for i in range(1, n):
		c_s = p_s ^ li[i]
		if c_s == 0:
			sol += i
		if c_s in tmp.keys():
			sol += tmp[c_s][1] * (i - 1) - tmp[c_s][0]
			tmp[c_s][0] += i
			tmp[c_s][1] += 1
		else:
			tmp[c_s] = [i, 1]
		p_s = c_s
	print(sol)


t = int(input())
for ankit in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	m = 0
	xorArr = [0 for _ in range(n)]
	mp = dict()
	xorArr[0] = arr[0]
	for i in range(1, n):
		xorArr[i] = xorArr[i - 1] ^ arr[i]
	for i in range(n):
		tmp = m ^ xorArr[i]
		if tmp in mp.keys():
			ans = ans + mp[tmp][0] * (i - mp[tmp][1]) - 1 + mp[tmp][2]
		if xorArr[i] == m:
			ans += i
		if mp.get(xorArr[i]) != None:
			mp[xorArr[i]] = [mp[xorArr[i]][0] + 1, i, mp[xorArr[i]][2] + mp[tmp][0] * (i - mp[tmp][1]) - 1]
		else:
			mp[xorArr[i]] = [1, i, 0]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	pr_xor = [0] * 10 ** 6
	pr_xor[0] = 1
	last_index = [0] * 10 ** 6
	last_index[0] = -1
	prev_xor_cnt = [0] * 10 ** 6
	prev_xor_cnt[0] = 1
	prev_ans = [0] * 10 ** 6
	xor_val = 0
	ans = 0
	for (idx, ele) in enumerate(lst):
		xor_val ^= ele
		if pr_xor[xor_val]:
			ele_cnt = idx - last_index[xor_val]
			prev_ans[xor_val] = prev_ans[xor_val] + ele_cnt * prev_xor_cnt[xor_val] - 1
		pr_xor[xor_val] = 1
		prev_xor_cnt[xor_val] += 1
		last_index[xor_val] = idx
		ans += prev_ans[xor_val]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	c = {0: [0]}
	for (i, x) in enumerate(a):
		s ^= x
		c.setdefault(s, []).append(i + 1)
	s = 0
	for (k, v) in c.items():
		l = len(v) - 1
		if not l:
			continue
		x = sum(((v[i] - v[i - 1] - 1) * i * (l + 1 - i) for i in range(1, l + 1)))
		y = sum((i * (l - i) for i in range(1, l)))
		s += x + y
	print(s)


class C:

	def __init__(self, k):
		self.sum = k + 1
		self.cnt = 1
		self.res = 0

	def nxt(self, k):
		self.res += k * self.cnt - self.sum
		self.sum += k + 1
		self.cnt += 1
t = int(input())
for _ in range(t):
	n = int(input())
	d = {}
	x = 0
	for (i, v) in enumerate(map(int, input().split())):
		if x in d:
			d[x].nxt(i)
		else:
			d[x] = C(i)
		x ^= v
	if x in d:
		d[x].nxt(n)
	print(sum((x.res for x in d.values())))


import math
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	Result = 0
	XOR_list = [0] * 1000000
	Length = [0] * 1000000
	B = [0] * 1000000
	XOR = 0
	XOR_list[0] = 1
	B[0] = -1
	for i in range(N):
		j = 0
		XOR = XOR ^ A[i]
		if XOR_list[XOR]:
			j = i - B[XOR]
			Length[XOR] = Length[XOR] + (XOR_list[XOR] * j - 1)
			Result = Result + Length[XOR]
		B[XOR] = i
		XOR_list[XOR] = XOR_list[XOR] + 1
	print(Result)


from itertools import combinations
t = int(input())
for c in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = [0]
	for i in range(n):
		l.append(a[i] ^ l[-1])
	d = {}
	for j in range(n + 1):
		if l[j] in d:
			d[l[j]] += [j]
		else:
			d[l[j]] = [j]
	res = 0
	for x in d.values():
		le = len(x)
		for s in range(le):
			res += (2 * s + 1 - le) * x[s]
		res -= le * (le - 1) // 2
	print(res)


from collections import defaultdict as dd

def sumPair(arr, n):
	s = 0
	for i in range(n - 1, -1, -1):
		s += i * arr[i] - (n - 1 - i) * arr[i]
	return s
t = int(input())
for _ in range(t):
	n = int(input())
	d = dd(list)
	arr = list(map(int, input().split()))
	d[0] = [-1]
	x_sum = 0
	ans = 0
	tc = 0
	s = 0
	for i in range(n):
		x_sum ^= arr[i]
		temp = d.get(x_sum)
		if d.get(x_sum) != None:
			d[x_sum].append(i)
		else:
			d[x_sum] = [i]
	for i in d:
		l = len(d[i])
		if l > 1:
			sp = sumPair(d[i], l)
			c = l * (l - 1) // 2
			tc += c
			s += sp
	print(s - tc)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	xorsum = []
	xor = 0
	xorsum.append(xor)
	for i in range(len(a)):
		xor ^= a[i]
		xorsum.append(xor)
	xordict = dict()
	for i in range(len(xorsum)):
		if xorsum[i] in xordict:
			xordict[xorsum[i]].append(i)
		else:
			xordict[xorsum[i]] = [i]
	ans = 0
	for key in xordict:
		for i in range(1, len(xordict[key])):
			x = i * xordict[key][i] - i - sum(xordict[key][:i])
			ans += x
	print(ans)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	ans = 0
	xor_arr = [0] * 1000000
	lgth = [0] * 1000000
	a = [0] * 1000000
	xor = 0
	xor_arr[0] = 1
	a[0] = -1
	for i in range(n):
		c = 0
		xor = xor ^ A[i]
		if xor_arr[xor]:
			c = i - a[xor]
			lgth[xor] = lgth[xor] + (xor_arr[xor] * c - 1)
			ans += lgth[xor]
		a[xor] = i
		xor_arr[xor] += 1
	print(ans)


from collections import defaultdict
T = int(input())
for k in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	count = 0
	dic = defaultdict(list)
	prefixArr = [0] * N
	prefixArr[0] = arr[0]
	for i in range(1, N):
		prefixArr[i] = prefixArr[i - 1] ^ arr[i]
	for i in range(1, N + 1):
		temp = prefixArr[i - 1]
		x = dic[temp]
		if temp == 0:
			count += i - 1
		dic[temp].append(i)
	for i in list(dic.keys()):
		y = len(dic[i])
		z = dic[i]
		if y > 1:
			x = 0
			for m in range(1, y):
				x += m * (z[m] - z[m - 1]) - 1
				count += x
	print(count)


x = int(input())
for m in range(x):
	y = int(input())
	l = list(map(int, input().split(' ')))
	count = 0
	for i in range(y - 1):
		f = l[i]
		for j in range(i + 1, y):
			f = f ^ l[j]
			if f == 0:
				count += j - i
	print(count)


t = int(input())
while t:
	t -= 1
	s = int(input())
	lis = list(map(int, input().split(' ')))
	xor_lis = [0 for i in range(len(lis) + 1)]
	i = 1
	for v in lis:
		xor_lis[i] = xor_lis[i - 1] ^ v
		i += 1
	dic = {}
	for (i, val) in enumerate(xor_lis):
		if val in dic.keys():
			dic[val].append(i)
		else:
			dic[val] = [i]
	ans = 0
	for key in dic.keys():
		lis = dic[key]
		if len(lis) <= 1:
			continue
		length = len(lis)
		for i in range(length):
			ans += i * lis[i] - (length - 1 - i) * lis[i]
		ans -= length * (length - 1) / 2
	print(int(ans))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = [a[0]]
	c = 0
	(v, r) = ({}, {})
	v[d[0]] = 0
	r[d[0]] = 0
	for j in range(1, n):
		d.append(d[j - 1] ^ a[j])
		v[d[j]] = 0
		r[d[j]] = 0
	for k in range(n):
		if v[d[k]] > 0:
			if d[k] == 0:
				c += k
				c += (k - 1) * v[d[k]] - r[d[k]]
				v[d[k]] += 1
				r[d[k]] += k
			else:
				c += (k - 1) * v[d[k]] - r[d[k]]
				v[d[k]] += 1
				r[d[k]] += k
		else:
			if d[k] == 0:
				c += k
			v[d[k]] += 1
			r[d[k]] += k
	print(c)


t = int(input())
while t:
	n = int(input())
	z = input().split()
	for i in range(n):
		z[i] = int(z[i])
	XOR = 0
	prefix = [0] * n
	for i in range(n):
		XOR = XOR ^ z[i]
		prefix[i] = XOR
	dict1 = {}
	for i in range(n):
		dict1.setdefault(prefix[i], []).append(i)
	count = 0
	for (i, j) in dict1.items():
		if len(j) > 1:
			for k in range(len(j)):
				count += (2 * (k + 1) - len(j) - 1) * j[k]
			count -= len(j) * (len(j) - 1) / 2
		if i == 0:
			for k in range(len(j)):
				count += j[k]
	t -= 1
	print(int(count))


def dictt(arr):
	Dict = {}
	Dict[0] = [-1]
	for (i, val) in enumerate(arr):
		if val not in Dict:
			Dict[val] = [i]
		else:
			Dict[val].append(i)
	count = 0
	for keys in Dict:
		s = len(Dict[keys])
		if s >= 2:
			k = s - 1
			j = s - 1
			while j >= 0:
				count += k * Dict[keys][j]
				k -= 2
				j -= 1
		count -= s * (s - 1) // 2
	print(count)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	prefix = [0] * n
	prefix[0] = arr[0]
	for i in range(1, n):
		prefix[i] = prefix[i - 1] ^ arr[i]
	dictt(prefix)


t = int(input())
for _ in range(t):
	n = int(input())
	xrr = list(map(int, input().split()))
	a1 = list()
	a2 = list()
	res = 0
	a = xrr[0]
	a1 = [0] * 1000000
	a2 = [0] * 1000000
	a3 = list(range(1000001))
	a1[xrr[0]] = 0
	a2[xrr[0]] += 1
	prev1 = 0
	xr = 0
	pos = 0
	for i in range(1, n):
		xr = xrr[i] ^ xr
		prev2 = 0
		pos = 0
		pos = a3[xr]
		prev2 = prev1
		res += i * a2[pos] - a1[pos]
		a1[prev2] += i
		a2[prev2] += 1
		prev1 = pos
	print(res)


for i in range(int(input())):
	a = int(input())
	b = [x for x in map(int, input().split())]
	c = [0] * a
	c[0] = b[0]
	count = 0
	for j in range(1, a):
		c[j] = c[j - 1] ^ b[j]
	dic = dict()
	for k in range(a):
		ans = 0
		n = 0
		if c[k] not in dic.keys():
			dic[c[k]] = [k, 0, 1]
		elif dic[c[k]][1] == 0:
			ans = k - dic[c[k]][0] - 1
			dic[c[k]] = [k, ans, 2]
		else:
			ans = dic[c[k]][1] + dic[c[k]][2] * (k - dic[c[k]][0]) - 1
			n = dic[c[k]][2] + 1
			dic[c[k]] = [k, ans, n]
		if c[k] == 0:
			count += k
		count += dic[c[k]][1]
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	dic = {0: [1, -1, 0]}
	temp = 0
	ans = 0
	for i in range(n):
		temp = temp ^ arr[i]
		if temp in dic:
			k = dic[temp][2] + (i - dic[temp][1]) * dic[temp][0] - 1
			ans += k
			dic[temp][0] += 1
			dic[temp][2] = k
			dic[temp][1] = i
		else:
			dic[temp] = [1, i, 0]
	print(ans)


def prefixXor(arr):
	output = [0]
	temp = 0
	out = dict()
	out[0] = [1, 0]
	ans = 0
	for item in range(len(arr)):
		temp ^= arr[item]
		output.append(temp)
		if not output[item + 1] in out.keys():
			out[output[item + 1]] = [0, 0]
		count = out[output[item + 1]][0]
		su = out[output[item + 1]][1]
		ans += count * (item + 1) - count - su
		count += 1
		out[output[item + 1]][0] = count
		out[output[item + 1]][1] += item + 1
	return ans
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	print(prefixXor(arr))


from functools import reduce
from operator import xor
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(1, n):
		for j in range(i):
			res = reduce(xor, a[j:j + n - i + 1])
			if res == 0:
				ans += n - i
	print(ans)


def reverse_indexed_map(myList):
	map_of_values = {}
	for (index, val) in enumerate(myList):
		if val not in map_of_values.keys():
			map_of_values[val] = [index]
		else:
			map_of_values[val] += [index]
	return map_of_values

def number_of_triplets(indexed_values):
	num = 0
	if 0 in indexed_values.keys():
		indexed_values[0] += [-1]
	for (key, indices_list) in indexed_values.items():
		indices_list.sort(reverse=True)
		length = len(indices_list) - 1
		l = len(indices_list)
		for i in indices_list:
			num += length * i
			length -= 2
		num -= int(l * (l - 1) / 2)
	return num
try:
	tests = int(input())
except:
	quit()
while tests != 0:
	number_of_integers = int(input())
	input_list = [int(x) for x in input().split()]
	for (index, val) in enumerate(input_list):
		if index == 0:
			continue
		else:
			input_list[index] = input_list[index - 1] ^ val
	temp = reverse_indexed_map(input_list)
	answer = number_of_triplets(temp)
	print(answer)
	tests -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	px = [0]
	x = 0
	d = {0: [0]}
	for i in range(n):
		x = x ^ l[i]
		px.append(x)
		if x not in d:
			d[x] = [i + 1]
		else:
			d[x].append(i + 1)
	gsum = 0
	for i in d:
		if len(d[i]) > 1:
			summ = d[i][0]
			for j in range(1, len(d[i])):
				gsum += d[i][j] * j - summ - j
				summ += d[i][j]
	print(gsum)


def gudv(n, l):
	c = 0
	b = 0
	d = {}
	d[0] = [0, 1]
	for i in range(n):
		b = b ^ l[i]
		if b in d:
			c += d[b][1] * i - d[b][0]
			d[b][0] += i + 1
			d[b][1] += 1
		else:
			d[b] = [i + 1, 1]
	print(c)
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	gudv(n, l)


T = int(input())
for _ in range(0, T):
	N = int(input())
	arr = list(map(int, input().split()))
	prexor = []
	cnt = 0
	prexor.append(0)
	tp = 0
	for i in range(N):
		tp ^= arr[i]
		prexor.append(tp)
	dict1 = dict()
	for i in range(0, len(prexor)):
		sm = prexor[i]
		if sm not in dict1.keys():
			dict1[prexor[i]] = [i + 1]
		else:
			klis = dict1[prexor[i]]
			klis.append(i + 1)
			dict1[prexor[i]] = klis
	kys = list(dict1.keys())
	for i in range(0, len(kys)):
		li = list(dict1[kys[i]])
		l = len(li)
		if l > 1:
			for j in range(l - 1):
				cnt += (l - j - 1) * ((li[j + 1] - li[j]) * (j + 1) - 1)
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	prefix_xor = []
	z = 0
	prefix_xor.append(0)
	for i in range(n):
		z = z ^ a[i]
		prefix_xor.append(z)
	p_dict = dict()
	for i in range(n + 1):
		p_dict[prefix_xor[i]] = []
	for i in range(n + 1):
		p_dict[prefix_xor[i]].append(i)
	for (i, j) in p_dict.items():
		if len(j) != 1:
			l = len(j)
			for i in range(l - 1):
				ans += (j[i + 1] - j[i]) * (i + 1) * (l - i - 1)
				ans -= l - i - 1
	print(ans)


t = int(input())
while t:
	n = int(input())
	ans = 0
	li = list(map(int, input().split()))
	li = [0] + li
	xor = [0]
	for i in range(1, n + 1):
		xor.append(xor[i - 1] ^ li[i])
	di = dict()
	for i in range(0, n + 1):
		if xor[i] in di:
			di[xor[i]].append(i)
		else:
			di[xor[i]] = [i]
	for val in di.values():
		l = len(val)
		if l >= 2:
			ans -= l * (l - 1) // 2
			const = -(l - 1)
			for i in val:
				ans += const * i
				const += 2
	print(ans)
	t = t - 1