You are given a set $S$ and $Q$ queries. Initially, $S$ is empty. In each query:
- You are given a positive integer $X$.
- You should insert $X$ into $S$.
- For each $y \in S$ before this query such that $y \neq X$, you should also insert $y \oplus X$ into $S$ ($\oplus$ denotes the XOR operation).
- Then, you should find two values $E$ and $O$: the number of elements of $S$ with an even number of $1$-s and with an odd number of $1$-s in the binary representation, respectively.
Note that a set cannot have duplicate elements, so if you try to insert into $S$ an element that is already present in $S$, then nothing happens.

-----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 $Q$.
- Each of the next $Q$ lines contains a single integer $X$ describing a query.

-----Output-----
For each query, print a single line containing two space-separated integers $E$ and $O$.

-----Constraints-----
- $1 \le T \le 5$
- $1 \le Q, X \le 10^5$

-----Subtasks-----
Subtask #1 (30 points):
- $1 \le Q \le 1,000$
- $1 \le X \le 128$
Subtask #2 (70 points): original constraints

-----Example Input-----
1
3
4
2
7

-----Example Output-----
0 1
1 2
3 4

-----Explanation-----
Example case 1:
- Initially, the set is empty: $S = \{\}$.
- After the first query, $S = \{4\}$, so there is only one element with an odd number of $1$-s in the binary representation ("100").
- After the second query, $S = \{4,2,6\}$, there is one element with an even number of $1$-s in the binary representation ($6$ is "110") and the other two elements have an odd number of $1$-s.
- After the third query, $S = \{4,2,6,7,3,5,1\}$.

Difficulty: interview

Starter code:

Solutions:
# fast io
import sys
def fop(s): sys.stdout.write(str(s)+'\n')
def fip(): return sys.stdin.readline()
fintinp = lambda : int(fip()) 
def flistinp(func= int): return list(map(func,fip().split())) 
def fnsepline(n,func=str): return [func(fip()) for _ in range(n)]
#-------------------code------------------------
def even(x):
 x = bin(x).count('1')
 return x%2==0
 
for _ in range(fintinp()):
 q =fintinp()
 o = e =0 
 nums = set()
 for qn in range(q):
  qn = fintinp()
  if qn not in nums:
   if even(qn): e+=1 
   else: o+=1 
   
   for n in set(nums):
    x = n^qn
    if x not in nums:
     if even(x): e+=1 
     else: o+=1 
     
     nums.add(x)
    
  nums.add(qn)
  print(e,o)


# fast io
import sys
def fop(s): sys.stdout.write(str(s)+'\n')
def fip(): return sys.stdin.readline()
fintinp = lambda : int(fip()) 
def flistinp(func= int): return list(map(func,fip().split())) 
def fnsepline(n,func=str): return [func(fip()) for _ in range(n)]
#-------------------code------------------------
def even(x):
 x = bin(x).count('1')
 return x%2==0
 
for _ in range(fintinp()):
 q =fintinp()
 o = e =0 
 nums = set()
 for qn in range(q):
  qn = fintinp()
  if qn not in nums:
   if even(qn): e+=1 
   else: o+=1 
   
   for n in set(nums):
    x = n^qn
    if x not in nums:
     if even(x): e+=1 
     else: o+=1 
     
     nums.add(x)
    
  nums.add(qn)
  print(e,o)


from sys import stdin, stdout
from math import ceil
import numpy as np
from numpy.linalg import matrix_power


def parity(n):
 return bin(n)[2:].count('1') % 2


def solve():
 for _ in range(int(input())):
  s = set()
  q = int(input())
  p = [0, 0]
  while q:
   q -= 1
   x = int(input())
   if s == set():
    p[parity(x)] += 1
    s.add(x)
   else:
    if x not in s:
     se = set()
     for j in s:
      se.add(j ^ x)
      p[parity(j ^ x)] += 1
     s = s.union(se)
     s.add(x)
     p[parity(x)] += 1
   print(p[0], p[1])


def __starting_point():
 solve()

__starting_point()

import collections
def bits(x):
 return bin(x).count('1')
t=int(input())
for _ in range(t):
 q=int(input())
 s=[]
 d=collections.defaultdict(lambda:-1)
 e=0
 o=0
 p=-1
 for i in range(q):
  x=int(input())
  # print(d)
  if d[x]!=-1:
   print(e,o)
   continue
  s.append(x)
  d[x]=1
  #z=len(s)
  for j in s:
   if j!=x:
    l=j^x
    if d[l]!=-1:
     continue
    s.append(l)
    d[l]=1
   
  for j in range(p+1,len(s)):
   p=j
   if bits(s[j])%2==0:
    e=e+1
   elif bits(s[j])%2!=0:
    o=o+1
  print(e,o)


import collections
t = int(input())
for _ in range(t):
 q = int(input())
 s = collections.defaultdict(lambda : -1)
 e , o = 0 , 0
 for __ in range(q):
  x = int(input())
  d = []
  # print(s)
  dd = list(s)
  if s[x] == -1:
   for i in dd:
    xo = i^x
    d.append(xo)
   d=set(d)
   for i in d:
    if s[i]==-1:
     if bin(i).count('1')%2==0:
      e+=1
     else:
      o+=1
     s[i]=1
   s[x]=1
   if bin(x).count('1')%2==0:
    e+=1
   else:
    o+=1
   for i in d:
    s[i]=1
  print(e,o)





t = int(input())
for _ in range(t):
 q = int(input())
 s = []
 e , o = 0 , 0
 for __ in range(q):
  x = int(input())
  d = []
  if x not in s:
   for i in s:
    xo = i^x
    d.append(xo)
   d=set(d)
   for i in d:
    if i not in s:
     if bin(i).count('1')%2==0:
      e+=1
     else:
      o+=1
   s.append(x)
   if bin(x).count('1')%2==0:
    e+=1
   else:
    o+=1
   for i in d:
    s.append(i)
  print(e,o)





t = int(input())
for _ in range(t):
 q = int(input())
 s = []
 e , o = 0 , 0
 for __ in range(q):
  x = int(input())
  d = []
  if x not in s and x not in d:
   for i in s:
    xo = i^x
    if xo not in s and xo not in d:
     d.append(xo)
     if bin(xo).count('1')%2==0:
      e+=1
     else:
      o+=1
   s.append(x)
   if bin(x).count('1')%2==0:
    e+=1
   else:
    o+=1
  
  
  for i in d:
   s.append(i)
  print(e,o)




t=int(input())
for i in range(t):
 n=int(input())
 a=[]
 s=set()
 cta,ctb=0,0
 while(n!=0):
  x=int(input())
  m=len(a)
  if(x not in s):
   s.add(x)
   a.append(x)
   s2=bin(x).count('1')
   if(s2%2==0):
    cta+=1
   else:
    ctb+=1
   for i in range(m):
    y=x^a[i]
    #print(y)
    if(y not in s):
     s.add(y)
     a.append(y)
     s2=bin(y).count('1')
     if(s2%2==0):
      cta+=1
     else:
      ctb+=1
  print(cta,ctb)
  n-=1

from collections import Counter

t = int(input())

for _ in range(t):
 q = int(input())
 orig_set = set()
 orig_set.add(0)
 E, O = 0, 0

 for row in range(q):
  x = int(input())
  if x in orig_set:
   print(E, O)
  else:
   l = []
   for i in orig_set:
    elem = i ^ x 
    if Counter(bin(elem)[2:])['1'] % 2 == 1:
     O += 1
    else:
     E += 1
    l.append(elem)
   
   for e in l:
    orig_set.add(e)
   print(E, O)

from collections import Counter


a= int(input())
while a!=0:
 b = int(input())
 original = list()
 original.append(0)
 ev,od=0,0

 for i in range(b):

  c = int(input())
  if c in original:
   print(ev,od)
   continue
  else:
   for j in range(len(original)):
    p = c^original[j]
    if Counter(bin(p))['1']%2 == 0:
     ev+=1
    else:
     od+=1
    original.append(p)
   print(ev,od)
  

 a-=1


from collections import Counter


a = int(input())
while a!=0:

 b = int(input())
 mylist = list()
 ev, od = 0, 0
 for i in range(b):
  c = int(input())

  fla=0

  for j in range(len(mylist)):


   if c==mylist[j]:
    print(ev,od)
    fla=1
    break
  if fla==1:
   continue

  temp = list()
  for j in range(len(mylist)):
   if c != mylist[j]:

    mylist.append(c^mylist[j])
    r = c^mylist[j]
    elem = mylist[j] ^ c
    
    if Counter(bin(elem)[2:])['1'] % 2 == 1:
     od += 1
    else:
     ev += 1
    mylist.append(r)
  mylist = list(set(mylist))
  mylist.append(c)


  elem = mylist[len(mylist)-1]

  if Counter(bin(elem)[2:])['1'] % 2 == 1:
   od += 1
  else:
   ev += 1



  print(ev,od)






 a-=1



def countSetBits(n):
 count = 0
 while (n):
  count += n & 1
  n >>= 1
 return count



a = int(input())
while a!=0:

 b = int(input())
 mylist = list()
 ev, od = 0, 0
 for i in range(b):
  c = int(input())

  fla=0

  for j in range(len(mylist)):


   if c==mylist[j]:
    print(ev,od)
    fla=1
    break
  if fla==1:
   continue

  temp = list()
  for j in range(len(mylist)):
   if c != mylist[j]:

    mylist.append(c^mylist[j])
    r = c^mylist[j]
    p = countSetBits(r)

    if p % 2 == 0:
     ev += 1
    else:
     od += 1

  mylist.append(c)
  
  p = countSetBits(mylist[len(mylist)-1])

  if p % 2 == 0:
   ev += 1
  else:
   od += 1


  print(ev,od)






 a-=1



def countSetBits(n):
 count = 0
 while (n):
  count += n & 1
  n >>= 1
 return count



a = int(input())
while a!=0:

 b = int(input())
 mylist = list()
 ev, od = 0, 0
 for i in range(b):
  c = int(input())

  fla=0
  for j in range(len(mylist)):
   if c==mylist[j]:
    print(ev,od)
    fla=1
    break
  if fla==1:
   continue
  ev, od = 0, 0
  for j in range(len(mylist)):
   if c != mylist[j]:

    mylist.append(c^mylist[j])

  mylist.append(c)
  mylist = list(set(mylist))
  
  for j in range(len(mylist)):
   p = countSetBits(mylist[j])


   if p%2 == 0:
    ev+=1
   else:
    od+=1
  print(ev,od)






 a-=1



def countSetBits(n):
 count = 0
 while (n):
  count += n & 1
  n >>= 1
 return count



a = int(input())
while a!=0:

 b = int(input())
 mylist = list()

 for i in range(b):
  c = int(input())
  ev, od = 0, 0
  for j in range(len(mylist)):
   if c != mylist[j]:

    mylist.append(c^mylist[j])

  mylist.append(c)
  mylist = list(set(mylist))

  for j in range(len(mylist)):
   p = countSetBits(mylist[j])


   if p%2 == 0:
    ev+=1
   else:
    od+=1
  print(ev,od)






 a-=1


from collections import Counter

t = int(input())

for _ in range(t):
 q = int(input())
 orig_set = set()
 orig_set.add(0)
 E, O = 0, 0

 for row in range(q):
  x = int(input())
  if x in orig_set:
   print(E, O)
  else:
   l = []
   for i in orig_set:
    elem = i ^ x 
    if Counter(bin(elem)[2:])['1'] % 2 == 1:
     O += 1
    else:
     E += 1
    l.append(elem)
   
   for e in l:
    orig_set.add(e)
   print(E, O)

from collections import Counter

t = int(input())

for _ in range(t):
 q = int(input())
 orig_set = set()

 for row in range(q):
  E, O = 0, 0
  x = int(input())
  for i in set(orig_set):
   if i != x:
    orig_set.add(i ^ x)
  orig_set.add(x)

  for elem in orig_set:
   if Counter(bin(elem)[2:])['1'] % 2:
    O += 1
   else:
    E += 1

  print(E, O)

import math

def countSetBits(i):

 i = i - ((i >> 1) & 0x55555555)
 i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
 return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
a = int(input())
while a!=0:
 mylist = list()
 b= int(input())
 count_even = 0
 count_odd = 0
 for j in range(b):

  c = int(input())
  t=0
  for i in range(len(mylist)):
   if(mylist[i] == c):
    t=1
    break
  if(t == 0):
   for i in range(len(mylist)):
    if(mylist[i] != c):
     p = mylist[i]^c
     q = math.log2(p)
     if(q == int(q)):
      count_odd+=1
     else:
      if(countSetBits(p)%2 == 0):
       count_even+=1
      else:
       count_odd+=1
     mylist.append(p)
    else:
     mylist.append(c)
   mylist.append(c)
   p = math.log2(c)
   if(p == int(p)):
    count_odd+=1
   else:
    if(countSetBits(c)%2 ==0):
     count_even+=1
    else:
     count_odd+=1
  print(count_even,count_odd)






 a-=1





import math

def countSetBits(n):
 count = 0
 while (n):
  n &= (n - 1)
  count += 1

 return count

a = int(input())
while a!=0:
 mylist = list()
 b= int(input())
 count_even = 0
 count_odd = 0
 for j in range(b):

  c = int(input())
  t=0
  for i in range(len(mylist)):
   if(mylist[i] == c):
    t=1
    break
  if(t == 0):
   for i in range(len(mylist)):
    if(mylist[i] != c):
     p = mylist[i]^c
     q = math.log2(p)
     if(q == int(q)):
      count_odd+=1
     else:
      if(countSetBits(p)%2 == 0):
       count_even+=1
      else:
       count_odd+=1
     mylist.append(p)
    else:
     mylist.append(c)
   mylist.append(c)
   p = math.log2(c)
   if(p == int(p)):
    count_odd+=1
   else:
    if(countSetBits(c)%2 ==0):
     count_even+=1
    else:
     count_odd+=1
  print(count_even,count_odd)






 a-=1





T = int(input())
for a in range(T):
 Q = int(input())
 l2 = []
 even = 0
 odd = 0
 for _ in range(Q):

  l3 =[]
  z = int(input())
  if z not in l2:
   x = str(bin(z))

   if (x.count('1') % 2) == 0:
    even += 1
   else:
    odd += 1
   for w in l2:
    l3.append(w ^ z)
    x = str(bin(w ^ z))

    if (x.count('1') % 2) == 0:
     even += 1
    else:
     odd += 1
   l2.append(z)
   l2.extend(l3)

  print(even,end = " ")
  print(odd)

















T = int(input())
for a in range(T):
 Q = int(input())
 l2 = []
 for _ in range(Q):
  even = 0
  odd = 0
  l3 =[]
  z = int(input())
  if z not in l2:
   for w in l2:

    l3.append(w ^ z)
   l3.append(z)
   l2.extend(l3)

  for q in l2:
   x =str(bin(q))

   if (x.count('1') % 2) == 0:
    even += 1
   else:
    odd += 1
  print(even ,end = " ")
  print(odd)


















def eo(n):
 cnt=0
 while(n):
  n&=n-1
  cnt+=1
 return cnt



for _ in range(int(input())):
 arr=[]
 even=0
 odd=0
 check={}
 for _ in range(int(input())):
  x=int(input())
  if x not in arr:
   for i in range(len(arr)):
    y=x^arr[i]
    if y not in arr:
     check[y]=0
     arr.append(y)
     j=eo(y)
     if j%2==0:
      even+=1
     else:
      odd+=1
  if x not in arr:
   check[x]=0
   arr.append(x)
   j=eo(x)
   if j%2==0:
    even+=1
   else:
    odd+=1
  print(even,odd)

def eo(n):
 cnt=0
 while(n):
  n&=n-1
  cnt+=1
 return cnt



for _ in range(int(input())):
 arr=[]
 even=0
 odd=0
 check={}
 for _ in range(int(input())):
  x=int(input())
  if check.get(x)==None:
   for i in range(len(arr)):
    y=x^arr[i]
    if check.get(y)==None:
     check[y]=0
     arr.append(y)
     j=eo(y)
     if j%2==0:
      even+=1
     else:
      odd+=1
  if check.get(x)==None:
   check[x]=0
   arr.append(x)
   j=eo(x)
   if j%2==0:
    even+=1
   else:
    odd+=1
  print(even,odd)

def eo(n):
 cnt=0
 while(n):
  n&=n-1
  cnt+=1
 return cnt

def xor(a, b):
 ans = a^b
 return ans

for _ in range(int(input())):
 arr=[]
 even=0
 odd=0
 check={}
 for _ in range(int(input())):
  x=int(input())
  if check.get(x)==None:
   for i in range(len(arr)):
    y=xor(x, arr[i])
    if check.get(y)==None:
     check[y]=0
     arr.append(y)
     j=eo(y)
     if j%2==0:
      even+=1
     else:
      odd+=1
  if check.get(x)==None:
   check[x]=0
   arr.append(x)
   j=eo(x)
   if j%2==0:
    even+=1
   else:
    odd+=1
  print(even,odd)