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$.

Difficulty: interview

Starter code:

Solutions:
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())
 #print(xorArr)
 #print(a)
 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))

# cook your dish here
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]
   #print(sum)
   if(sum==0):
    count=count+(j-i)
   
 print(count)

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



# Function to call the actual solution
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


# Function to take input
def input_test():
 for _ in range(int(input())):
  n = int(input())
  # a, b = map(int, input().strip().split(" "))
  # a, b, c = map(int, input().strip().split(" "))
  li = list(map(int, input().strip().split(" ")))
  out = solution(li)
  print(out)

# Function to check test my code
def test():
 pass


input_test()
# test()


# cook your dish here
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])
   #print(res, a[j:j+n-i+1])
   if( res == 0 ):
    ans += n-i
    
 print(ans)

# cook your dish here
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 _ 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())
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)
  


import math

for _ in range(int(input())):
 N = int(input())
 Arr = [int(o) for o 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)

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)


# cook your dish here
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)

# cook your dish here
# import atexit
# import io
# import sys
#
#
# _INPUT_LINES = sys.stdin.read().splitlines()
# input = iter(_INPUT_LINES).__next__
# _OUTPUT_BUFFER = io.StringIO()
# sys.stdout = _OUTPUT_BUFFER
#
#
# @atexit.register
# def write():
#     sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
#
# # Brute force approach
# R = lambda :map(int,input().split())
# t = int(input())
# for i in range(t):
#     n = int(input())
#     lst = list(R())
#     cnt = 0
#     for i in range(n):
#         temp = 0
#         for j in range(i,n):
#             temp^=lst[j]
#             if temp==0:
#                 cnt+=j-i
#
#     print(cnt)
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 :list(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 i in range(1,len(xs)):
 #     xs[i]=xs[i-1]^xs[i]
 # print(xs)
 for x in xs:
  xor = xor ^ x
  if xor not in dict:
   dict[xor] = [i + 1]
  else:
   # for j in dict[xor]:
   #     count += (i + 1) - j - 1
   dict[xor].append(i + 1)
  i+=1
 ans = 0
 for i in list(dict.values()):
  if len(i)==1:
   continue
  else:
   ans+=(sumPairs(i,len(i)))


 # print(dict)
 print(ans)


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)

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):
   
   # check
   x = 0
   for y in a[i: k + 1]:
    x ^= y
   if x == 0:
    
    # update set
    for j in range(i + 1, k + 1):
     if (i, j, k) not in s:
      s.add((i, j, k))
      c += 1
   
 print(c)

# cook your dish here
# cook your dish here
t=int(input())
while t>0:
 n=int(input())
 inp=[int(i) for i in input().split()]
 #print(inp)
 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
 #print(xorarr)
 #print(mydict)
 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 
 #print(mydicts)
 
 for i in list(mydicts.keys()):
  sums=sums+mydicts[i][1]-(mydict[i]*(mydict[i]-1)/2)
  
 print(int(sums))
 #print(mydicts)


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))

# cook your dish here
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)
 
 #print(xors)
 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)

# cook your dish here
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)


# cook your dish here
test_cases = int(input())
for test in range(test_cases):
 n = int(input())
 seq = list(map(int, input().split()))
 
 triplets = 0
 for i in range(n):
  res = [0 for _ in range(n)]
  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)


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
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)
 # print(cnt)
 res=0
 for l in cnt:
  for k in range(len(cnt[l])-1):
   for j in range(k+1,len(cnt[l])):
    # print(l,cnt[l][k],cnt[l][j],abs(cnt[l][k]-cnt[l][j])-1)
    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()

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)

for _ 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)