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\}$.
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)
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)