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

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics

Constructive algorithms


Solutions:
from sys import stdin, stdout

def parity(n):
	return bin(n)[2:].count('1') % 2
t = int(stdin.readline())
for _ in range(t):
	x = [0, 0]
	s = set()
	n = int(stdin.readline())
	for i in range(n):
		z = int(stdin.readline())
		par = parity(z)
		if s == set():
			x[par] += 1
			s.add(z)
		elif z not in s:
			se = set()
			if par == 1:
				(e, o) = x
				x[1] += e
				x[0] += o
			else:
				(e, o) = x
				x[1] += o
				x[0] += e
			for j in s:
				se.add(j ^ z)
			s = s.union(se)
			s.add(z)
			x[par] += 1
		print(x[0], x[1])


def cnt_bits(x):
	result = 0
	while x > 0:
		if x % 2 == 1:
			result += 1
		x //= 2
	return result
t = int(input())
for i in range(t):
	l = set()
	q = int(input())
	odd = 0
	even = 0
	for j in range(q):
		a = int(input())
		if not a in l:
			new = set()
			for b in l:
				new.add(b ^ a)
				if cnt_bits(b ^ a) % 2 == 1:
					odd += 1
				else:
					even += 1
			l.add(a)
			if cnt_bits(a) % 2 == 1:
				odd += 1
			else:
				even += 1
			l |= new
		print(str(even) + ' ' + str(odd))


from collections import defaultdict
for _ in range(int(input())):
	q = int(input())
	d = defaultdict(int)
	s = set()
	(e, o) = (0, 0)
	x = int(input())
	d[x] = 1
	s.add(x)
	if bin(x)[2:].count('1') % 2 == 0:
		e += 1
	else:
		o += 1
	print(e, o)
	for _ in range(q - 1):
		x = int(input())
		temp = set()
		if x not in d:
			temp.add(x)
			d[x] = 1
			if bin(x)[2:].count('1') % 2 == 0:
				e += 1
			else:
				o += 1
			for i in s:
				t = x ^ i
				if t not in d:
					temp.add(t)
					d[t] = 1
					if bin(t)[2:].count('1') % 2 == 0:
						e += 1
					else:
						o += 1
			s = temp | s
		print(e, o)


def check(Num):
	s1 = 0
	while Num:
		Num = Num & Num - 1
		s1 += 1
	return s1
for t in range(int(input())):
	s = set()
	even_ones = 0
	odd_ones = 0
	Q = int(input())
	while Q:
		X = int(input())
		if X in s:
			Q -= 1
			print(even_ones, odd_ones)
			continue
		s1 = set()
		for elem in s:
			s1.add(elem ^ X)
		for elem in s1:
			s.add(elem)
		par = check(X)
		if par % 2:
			(even_ones, odd_ones) = (even_ones + odd_ones, odd_ones + even_ones + 1)
		else:
			(even_ones, odd_ones) = (even_ones + even_ones + 1, odd_ones + odd_ones)
		print(even_ones, odd_ones)
		Q -= 1
		s.add(X)


def count(n):
	cnt = 0
	while n > 0:
		if 1 & n == 1:
			cnt += 1
		n >>= 1
	return cnt
t = int(input())
for i in range(t):
	dict = {}
	q = int(input())
	e = 0
	o = 0
	for i1 in range(q):
		x = int(input())
		if i1 == 0:
			dict[x] = count(x)
			if dict[x] % 2 == 0:
				e += 1
			else:
				o += 1
		elif not x in dict.keys():
			dict[x] = count(x)
			if dict[x] % 2 == 0:
				e += 1
			else:
				o += 1
			dict2 = {}
			for j in dict:
				if j != x and (not j ^ x in dict.keys()):
					dict2[j ^ x] = count(j ^ x)
					if dict2[j ^ x] % 2 == 0:
						e += 1
					else:
						o += 1
			dict.update(dict2)
		print(e, o)


import sys
t = int(input())

def popcount(x):
	count = 0
	while x:
		count += x & 1
		x >>= 1
	return count
while t:
	q = int(input())
	s = set()
	(even, odd) = (0, 0)
	while q:
		x = int(input())
		if x not in s:
			tmp = list(s)
			for y in tmp:
				s.add(y ^ x)
				if popcount(y ^ x) % 2 == 0:
					even += 1
				else:
					odd += 1
			if popcount(x) % 2 == 0:
				even += 1
			else:
				odd += 1
			s.add(x)
		q -= 1
		sys.stdout.write(str(even) + ' ' + str(odd) + '\n')
	t -= 1


from collections import Counter
for _ in range(int(input())):
	q = int(input())
	initial = set()
	initial.add(0)
	(E, O) = (0, 0)
	for i in range(q):
		j = int(input())
		if j in initial:
			print(E, O)
		else:
			a = []
			for i in initial:
				e = i ^ j
				if Counter(bin(e)[2:])['1'] % 2 == 1:
					O += 1
				else:
					E += 1
				a.append(e)
			for k in a:
				initial.add(k)
			print(E, O)


def countSetBits(n):
	count = 0
	while n:
		dig = n % 2
		if dig:
			count += 1
		n //= 2
	return count
for t in range(int(input())):
	s = set()
	e = o = 0
	for q in range(int(input())):
		x = int(input())
		if x in s:
			print(e, o)
			continue
		t = set()
		for y in s:
			val = x ^ y
			t.add(val)
			if countSetBits(val) % 2:
				o += 1
			else:
				e += 1
		for y in t:
			s.add(y)
		s.add(x)
		if countSetBits(x) % 2:
			o += 1
		else:
			e += 1
		print(e, o)


import math

def countSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 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
					elif 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
			elif countSetBits(c) % 2 == 0:
				count_even += 1
			else:
				count_odd += 1
		print(count_even, count_odd)
	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 getParity(n):
	parity = 0
	while n:
		parity = ~parity
		n = n & n - 1
	return parity
testCases = int(input())
for x in range(testCases):
	oddCount = 0
	evenCount = 0
	integers = []
	check = {}
	lines = int(input())
	for x in range(lines):
		newInt = int(input())
		if check.get(newInt) == None:
			for y in integers:
				xorInt = newInt ^ y
				if check.get(xorInt) == None:
					integers.append(xorInt)
					check[xorInt] = 0
					if getParity(xorInt) == 0:
						evenCount += 1
					else:
						oddCount += 1
			integers.append(newInt)
			check[newInt] = 0
			if getParity(newInt) == 0:
				evenCount += 1
			else:
				oddCount += 1
			print(evenCount, oddCount)
		else:
			print(evenCount, oddCount)


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())
		if d[x] != -1:
			print(e, o)
			continue
		s.append(x)
		d[x] = 1
		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)


t = int(input())
for l in range(t):
	n = int(input())
	seti = set()
	x = []
	even = 0
	odd = 0
	while n != 0:
		a = int(input())
		if a not in seti:
			seti.add(a)
			x.append(a)
			k = bin(a).count('1')
			if k % 2 == 0:
				even += 1
			else:
				odd += 1
			for i in range(len(x)):
				xor = a ^ x[i]
				if xor not in seti:
					seti.add(xor)
					x.append(xor)
					p = bin(xor).count('1')
					if p % 2 == 0:
						even += 1
					else:
						odd += 1
		print(even - 1, odd)
		n -= 1


for h in range(int(input())):
	l = set()
	n = 0
	od = 0
	for i in range(int(input())):
		x = int(input())
		if x in l:
			print(n, '', od)
		elif len(l) - 2 * n == 1:
			if x in l:
				print(n, '', od)
			else:
				for j in list(l):
					l.add(x ^ j)
				n = 2 * n + 1
				od = 2 * od
				print(n, '', od)
				l.add(x)
		else:
			for j in list(l):
				l.add(x ^ j)
				if bin(x ^ j).count('1') % 2 == 0:
					n = n + 1
				else:
					od += 1
			l.add(x)
			if bin(x).count('1') % 2 == 0:
				n = n + 1
			else:
				od += 1
			print(n, '', od)


t = int(input())

def sb(num):
	s = bin(num)
	c = 0
	for i in s:
		if i == '1':
			c = c + 1
	if c % 2 == 0:
		return True
	else:
		return False
while t > 0:
	t = t - 1
	q = int(input())
	s1 = {}
	l = []
	od = 0
	ev = 0
	for i in range(0, q):
		e = int(input())
		if s1.get(e) == None:
			for k in range(len(l)):
				if l[k] != e:
					v = l[k] ^ e
					if s1.get(v) == None:
						s1[v] = 0
						l.append(v)
						if sb(v):
							ev = ev + 1
						else:
							od = od + 1
		if s1.get(e) == None:
			s1[e] = 0
			l.append(e)
			if sb(e):
				ev = ev + 1
			else:
				od = od + 1
		print(ev, end=' ')
		print(od)


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)


from collections import defaultdict

def bits(x):
	return bin(x).count('1')
t = int(input())
for _ in range(t):
	q = int(input())
	s = []
	dic = defaultdict(lambda : -1)
	odd = 0
	eve = 0
	viewed = -1
	for i in range(q):
		x = int(input())
		if dic[x] != -1:
			print(eve, odd)
			continue
		s.append(x)
		dic[x] = 1
		for j in s:
			if j != x:
				new = j ^ x
				if dic[new] != -1:
					continue
				s.append(new)
				dic[new] = 1
		for j in range(viewed + 1, len(s)):
			viewed = j
			if bits(s[j]) % 2 == 0:
				eve += 1
			if bits(s[j]) % 2 == 1:
				odd += 1
		print(eve, odd)


def findParity(x):
	a = bin(x).count('1')
	return a % 2
for _ in range(int(input())):
	e = 0
	o = 0
	s = set()
	for xyz in range(int(input())):
		x = int(input())
		if x not in s:
			n = set(s)
			for i in s:
				if i ^ x not in s:
					par = findParity(i ^ x)
					n.add(i ^ x)
					if par == 0:
						e += 1
					else:
						o += 1
					s = n
			par = findParity(x)
			if par == 0:
				e += 1
			else:
				o += 1
			s.add(x)
		print(e, o)


T = int(input())
for t in range(T):
	odd = 0
	even = 0
	q = int(input())
	s = set()
	for i in range(q):
		x = int(input())
		if not x in s:
			for j in s.copy():
				s.add(x ^ j)
				if bin(x ^ j).count('1') % 2:
					odd += 1
				else:
					even += 1
			s.add(x)
			if bin(x).count('1') % 2:
				odd += 1
			else:
				even += 1
		print(str(even) + ' ' + str(odd))


def bitcount(n):
	ans = 0
	while n:
		ans += n & 1
		n >>= 1
	return ans
for _ in range(int(input())):
	q = int(input())
	a = {0}
	(e, o) = (0, 0)
	for i in range(q):
		x = int(input())
		if x not in a:
			y = set()
			for j in a:
				y.add(j ^ x)
				if bitcount(j ^ x) & 1:
					o += 1
				else:
					e += 1
			a |= y
		print(e, o)


P = [0 for x in range(131072)]
P[1] = 1
for k in range(2, 131072):
	if k % 2 == 0:
		P[k] = P[k // 2]
	else:
		P[k] = 1 - P[k - 1]
t = int(input())
for i in range(t):
	Q = int(input())
	S = set()
	ET = 0
	OT = 0
	for k in range(Q):
		X = int(input())
		if not X in S:
			L = list(S)
			S.add(X)
			if P[X] == 1:
				OT += 1
			else:
				ET += 1
			for Y in L:
				v = X ^ Y
				S.add(v)
				if P[v] == 1:
					OT += 1
				else:
					ET += 1
		print(ET, OT)


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)):
				val = x ^ arr[i]
				if check.get(val) == None:
					check[val] = 0
					arr.append(val)
					j = bin(val).count('1')
					if j % 2 == 0:
						even += 1
					else:
						odd += 1
		if check.get(x) == None:
			check[x] = 0
			arr.append(x)
			j = bin(x).count('1')
			if j % 2 == 0:
				even += 1
			else:
				odd += 1
		print(even, odd)


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


P = [0 for x in range(131072)]
P[1] = 1
for k in range(2, 131072):
	if k % 2 == 0:
		P[k] = P[k // 2]
	else:
		P[k] = 1 - P[k - 1]
for _ in range(int(input())):
	Q = int(input())
	S = set()
	OC = 0
	EC = 0
	for k in range(Q):
		x = int(input())
		if x not in S:
			l = list(S)
			S.add(x)
			if P[x] == 1:
				OC += 1
			else:
				EC += 1
			for Y in l:
				v = x ^ Y
				S.add(v)
				if P[v] == 1:
					OC += 1
				else:
					EC += 1
		print(EC, OC)


def checkEvenParity(x):
	parity = 0
	while x != 0:
		x = x & x - 1
		parity += 1
	if parity % 2 == 0:
		return True
	else:
		return False
for _ in range(int(input())):
	q = int(input())
	ans = 0
	l = []
	s = set()
	e = 0
	o = 0
	for i in range(q):
		x = int(input())
		if x in s:
			print(e, o)
			continue
		else:
			ans = ans ^ x
			if ans in s:
				print(e, o)
				continue
			else:
				l.append(x)
				s.add(x)
				if checkEvenParity(x):
					e += 1
				else:
					o += 1
				l1 = len(l)
				for i in range(l1 - 1):
					temp = x ^ l[i]
					l.append(temp)
					s.add(temp)
					if checkEvenParity(temp):
						e += 1
					else:
						o += 1
			print(e, o)


def sb(num):
	c = bin(num).count('1')
	if c % 2 == 0:
		return True
	else:
		return False
for _ in range(int(input())):
	s1 = {}
	l = []
	od = 0
	ev = 0
	for _ in range(int(input())):
		e = int(input())
		if s1.get(e) == None:
			for k in range(len(l)):
				v = l[k] ^ e
				if s1.get(v) == None:
					s1[v] = 0
					l.append(v)
					if sb(v):
						ev = ev + 1
					else:
						od = od + 1
		if s1.get(e) == None:
			s1[e] = 0
			l.append(e)
			if sb(e):
				ev = ev + 1
			else:
				od = od + 1
		print(ev, od)


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)


ijk = []
ik = {}
uj = 'Cp1'
ugh = 'Contest2'
ugh = 90
t = int(input())
while t > 0:
	t -= 1
	q = int(input())
	x = set()
	e = 0
	o = 0
	ij = 0
	while q > 0:
		q -= 1
		k = int(input())
		if k in x:
			print(e, o)
			continue
		y = list(x)
		ij += 10
		for i in y:
			if i != k:
				x.add(i ^ k)
		x.add(k)
		pq = x.difference(set(y))
		for i in pq:
			cnts = 0
			while i:
				i = i & i - 1
				cnts += 1
			ij += 19
			if cnts % 2 == 0:
				e += 1
			else:
				o += 1
		print(e, o)
		ij += 90


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 = []
		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)


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)


import collections

def even_ones(num):
	ones = bin(num).count('1')
	if ones % 2 == 0:
		return True
	return False
T = int(input())
for t in range(T):
	Q = int(input())
	S = collections.defaultdict(lambda : -1)
	even = 0
	odd = 0
	for q in range(Q):
		x = int(input())
		if S[x] == 1:
			print(even, odd)
			continue
		S[x] = 1
		if even_ones(x):
			even += 1
		else:
			odd += 1
		S_tmp = list(S.keys())
		for i in range(len(S_tmp) - 1):
			y = S_tmp[i]
			z = y ^ x
			if S[z] == -1:
				S[z] = 1
				if even_ones(z):
					even += 1
				else:
					odd += 1
		print(even, odd)


for t in range(int(input())):
	s = set()
	even = odd = 0
	for q in range(int(input())):
		x = int(input())
		if x not in s:
			for val in list(s):
				xorVal = val ^ x
				if xorVal not in s:
					s.add(xorVal)
					numberOfBits = bin(xorVal).count('1')
					if numberOfBits % 2 == 0:
						even = even + 1
					else:
						odd = odd + 1
			numberOfBits = bin(x).count('1')
			if numberOfBits % 2 == 0:
				even = even + 1
			else:
				odd = odd + 1
			s.add(x)
		print(even, odd)


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

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)


import copy
for i in range(int(input())):
	s = set()
	e = 0
	o = 0
	for j in range(int(input())):
		yo = int(input())
		if yo not in s:
			e = 0
			o = 0
			s.add(yo)
			temp = []
			for k in s:
				if k != yo:
					temp.append(k ^ yo)
			for k in temp:
				if k not in s:
					s.add(k)
			for k in s:
				temps = bin(k)[2:]
				hey = temps.count('1')
				if hey % 2 == 0:
					e += 1
				else:
					o += 1
			print(e, o)
		else:
			print(e, o)


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


def BitCount(n):
	if n == 0:
		return 0
	else:
		return 1 + BitCount(n & n - 1)
for _ in range(int(input())):
	s = set()
	e = o = 0
	for t in range(int(input())):
		x = int(input())
		s1 = set()
		if len(s) == 0:
			s.add(x)
			if BitCount(x) % 2 == 0:
				e += 1
			else:
				o += 1
		if x not in s:
			for v in s:
				if x != v:
					y = x ^ v
				if BitCount(y) % 2 == 0:
					e += 1
				else:
					o += 1
				s1.add(y)
			if BitCount(x) % 2 == 0:
				e += 1
			else:
				o += 1
			s.add(x)
			s = s | s1
		print(e, o)


import collections

def even_ones(num):
	ones = bin(num).count('1')
	if ones % 2 == 0:
		return 1
	return 0
T = int(input())
for t in range(T):
	Q = int(input())
	D = collections.defaultdict(lambda : -1)
	S = []
	even = 0
	odd = 0
	for q in range(Q):
		x = int(input())
		if D[x] == 1:
			print(even, odd)
			continue
		D[x] = 1
		S.append(x)
		even += even_ones(x)
		l = len(S)
		for i in range(l - 1):
			y = S[i]
			z = y ^ x
			if D[z] == -1:
				D[z] = 1
				S.append(z)
				even += even_ones(z)
		odd = len(S) - even
		print(even, odd)


T = int(input())
for test_cases in range(0, T):
	Q = int(input())
	S = set([])
	even = 0
	odd = 0
	while Q > 0:
		X = int(input())
		if X not in S:
			P = S.copy()
			for i in P:
				if i != X:
					S.add(i ^ X)
			S.add(X)
			P = S - P
			for _ in P:
				if bin(_).count('1') % 2 == 0:
					even = even + 1
				else:
					odd = odd + 1
		print('%d %d' % (even, odd))
		Q = Q - 1


def bit(x):
	return bin(x).count('1')
for _ in range(int(input())):
	q = int(input())
	(e, o) = (0, 0)
	b = int(input())
	lst = []
	s = set()
	lst.append(b)
	s.add(b)
	if bit(b) % 2 == 0:
		e += 1
	else:
		o += 1
	print(e, o)
	for i in range(q - 1):
		x = int(input())
		if x not in s:
			lst.append(x)
			s.add(x)
			if bit(x) % 2 == 0:
				e += 1
			else:
				o += 1
			length = len(lst)
			for idx in range(length - 1):
				a = x ^ lst[idx]
				lst.append(a)
				s.add(a)
				if bit(a) % 2 == 0:
					e += 1
				else:
					o += 1
		print(e, o)


for i in range(int(input())):
	q = int(input())
	a = []
	s = set()
	(ctra, ctrb) = (0, 0)
	while q != 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:
				ctra += 1
			else:
				ctrb += 1
			for i in range(m):
				y = x ^ a[i]
				if y not in s:
					s.add(y)
					a.append(y)
					s2 = bin(y).count('1')
					if s2 % 2 == 0:
						ctra += 1
					else:
						ctrb += 1
		print(ctra, ctrb)
		q -= 1


def cbs(num):
	binary = bin(num)
	setBits = [ones for ones in binary[2:] if ones == '1']
	return len(setBits)
t = int(input())
for _ in range(t):
	n = int(input())
	s = set()
	e = 0
	o = 0
	for _ in range(n):
		a = int(input())
		if a not in s:
			for i in list(s):
				g = a ^ i
				if g not in s:
					b = cbs(g)
					if b % 2:
						o += 1
					elif b > 0:
						e += 1
					s.add(g)
			b = cbs(a)
			if b % 2:
				o += 1
			elif b > 0:
				e += 1
			s.add(a)
		print(e, o)


for _ in range(int(input())):
	S1 = set()
	S2 = set()
	q = int(input())
	for i in range(q):
		n = int(input())
		if n not in S1:
			for j in S1:
				S2.add(n ^ j)
			S1.add(n)
			S1 = S1.union(S2)
			O = 0
			e = 0
			for j in S1:
				cnt = bin(j).count('1')
				if cnt % 2 == 0:
					e += 1
				else:
					O += 1
		print(e, O)


import math

def bin(n):
	c = 0
	while n > 0:
		a = math.log(n, 2)
		n -= 2 ** int(a)
		c = c + 1
	if c % 2 == 0:
		return 1
	else:
		return 0
for _ in range(int(input())):
	n = int(input())
	s = set()
	odd = 0
	even = 0
	for i in range(n):
		a = int(input())
		if i == 0:
			s.add(a)
			if bin(a) == 0:
				odd += 1
			else:
				even += 1
		elif a not in s:
			for j in list(s):
				if j ^ a not in s:
					s.add(j ^ a)
					if bin(j ^ a) == 0:
						odd += 1
					else:
						even += 1
			if a not in s:
				s.add(a)
				if bin(a) == 0:
					odd += 1
				else:
					even += 1
		print(even, odd)


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)


def get_xor(a, b):
	return a ^ b

def get_side(val):
	c = 0
	while val:
		c += 1
		val &= val - 1
	if c % 2 == 0:
		return True
	else:
		return False
for _ in range(int(input())):
	q = int(input())
	check = {}
	l = []
	(e, o) = (0, 0)
	for __ in range(q):
		x = int(input())
		if check.get(x) == None:
			for j in range(len(l)):
				val = get_xor(x, l[j])
				if not check.get(val):
					l.append(val)
					check[val] = 0
					if get_side(val):
						e += 1
					else:
						o += 1
		if check.get(x) == None:
			l.append(x)
			check[x] = 0
			if get_side(x):
				e += 1
			else:
				o += 1
		print(e, o)


from operator import countOf
T = int(input())

def Parity(x, E, O):
	c = countOf(bin(x)[2:], '1')
	return (E + int(c % 2 == 0), O + int(c % 2 == 1))
for t in range(T):
	S = set()
	Q = int(input())
	(E, O) = (0, 0)
	for q in range(Q):
		X = int(input())
		if X not in S:
			for s in list(S):
				S.add(X ^ s)
				(E, O) = Parity(X ^ s, E, O)
			S.add(X)
			(E, O) = Parity(X, E, O)
		print(E, O)
	S.clear()


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


arr = [True] * 140000
for i in range(1, 140000):
	if bin(i).count('1') % 2 == 1:
		arr[i] = False
t = int(input())
for _ in range(t):
	s = set()
	odd = 0
	even = 0
	q = int(input())
	for _ in range(q):
		n = int(input())
		a = set()
		if n not in s:
			s.add(n)
			if arr[n]:
				(even, odd) = (even + 1 + even, odd + odd)
			else:
				(even, odd) = (even + odd, odd + even + 1)
			for i in s:
				if i != n:
					temp = i ^ n
					a.add(temp)
			s = s.union(a)
		print(even, odd)


import collections

def checkparity(a):
	parity = 0
	while a != 0:
		a = a & a - 1
		parity += 1
	if parity % 2 == 0:
		return True
	else:
		return False
test = int(input())
for _ in range(test):
	even = 0
	odd = 0
	lis = []
	beg = -1
	d = collections.defaultdict(lambda : -1)
	q = int(input())
	for i in range(q):
		x = int(input())
		if d[x] != -1:
			print(even, odd)
			continue
		lis.append(x)
		d[x] = 1
		for ele in lis:
			if ele != x:
				l = ele ^ x
				if d[l] != -1:
					continue
				lis.append(l)
				d[l] = 1
		for j in range(beg + 1, len(lis)):
			beg = j
			par = checkparity(lis[j])
			if par == True:
				even += 1
			else:
				odd += 1
		print(even, odd)


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


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 bin(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	e = 0
	o = 0
	dic = dict()
	for j in range(n):
		a = int(input())
		lst = list()
		if j == 0:
			dic[a] = 1
			m = bin(a)
			if m % 2 == 0:
				e += 1
			else:
				o += 1
			print(e, o)
		elif a not in dic and j > 0:
			for k in dic:
				lst.append(k ^ a)
				m = bin(k ^ a)
				if m % 2 == 0:
					e += 1
				else:
					o += 1
			for l in lst:
				dic[l] = 1
			dic[a] = 1
			m = bin(a)
			if m % 2 == 0:
				e += 1
			else:
				o += 1
			print(e, o)
		else:
			print(e, o)


for _ in range(int(input())):
	q = int(input())
	s = set()
	odd = 0
	even = 0
	for a in range(q):
		x = int(input())
		temp_list = []
		if x not in s:
			c = int(bin(x).count('1'))
			if c & 1:
				odd = odd + 1
			else:
				even = even + 1
			for elem in s:
				t = elem ^ x
				if t in s:
					continue
				temp_list.append(t)
				c = int(bin(t).count('1'))
				if c & 1:
					odd = odd + 1
				else:
					even = even + 1
			s.add(x)
			for e in temp_list:
				s.add(e)
		print(even, odd)


import collections
t = int(input())

def eo(l):
	x = []
	for i in l:
		if bin(i).count('1') % 2 == 0:
			x.append(1)
		else:
			x.append(0)
	return [x.count(1), x.count(0)]
while t:
	t -= 1
	s = []
	d = collections.defaultdict(lambda : -1)
	x = [0, 0]
	n = int(input())
	for i in range(n):
		p = int(input())
		if d[p] != -1:
			print(x[0], x[1])
			continue
		else:
			o = len(s)
			d[p] = 1
			s.append(p)
			for j in range(o):
				if s[j] != p:
					l = s[j] ^ p
					if d[l] != -1:
						continue
					s.append(l)
					d[l] = 1
			y = eo(s[len(s) - o - 1:])
			x[0] += y[0]
			x[1] += y[1]
			print(x[0], x[1])


for _ in range(int(input())):
	(odd, even) = (0, 0)
	M = [0] * 200077
	M[0] = 1
	q = int(input())
	for _ in range(q):
		x = int(input())
		if M[x] == 0:
			for i in range(0, 131072):
				if M[i] == 1 and M[i ^ x] == 0:
					M[i ^ x] = 1
					cnt = bin(i ^ x).count('1')
					if cnt & 1:
						odd += 1
					else:
						even += 1
		print(even, odd)


t = int(input())
for i in range(t):
	var1 = list()
	q = int(input())
	count1 = 0
	count2 = 0
	var2 = set()
	for j in range(q):
		x = int(input())
		if x not in var2:
			l = len(var1)
			for m in range(l):
				n = var1[m] ^ x
				var2.add(n)
				var1.append(n)
				s2 = bin(n).count('1')
				if s2 % 2 == 0:
					count1 = count1 + 1
				else:
					count2 = count2 + 1
			var1.append(x)
			var2.add(x)
			s2 = bin(x).count('1')
			if s2 % 2 == 0:
				count1 = count1 + 1
			else:
				count2 = count2 + 1
		print(count1, count2)


def check_even_parity(num):
	parity = 0
	while num != 0:
		num = num & num - 1
		parity = parity + 1
	if parity % 2 == 0:
		return True
	else:
		return False
t = int(input())
for i in range(t):
	q = int(input())
	number_dict = {}
	evens = 0
	odds = 0
	calculated_elements = 0
	number_set = []
	for j in range(q):
		x = int(input())
		if x not in number_dict:
			for number in number_set:
				xor_res = x ^ number
				if xor_res not in number_dict:
					if check_even_parity(xor_res):
						evens = evens + 1
					else:
						odds = odds + 1
					number_dict[xor_res] = 1
					number_set.append(xor_res)
			if check_even_parity(x):
				evens = evens + 1
			else:
				odds = odds + 1
			number_dict[x] = 1
			number_set.append(x)
		print(str(evens) + ' ' + str(odds))


import collections

def checkEvenParity(x):
	parity = 0
	while x != 0:
		x = x & x - 1
		parity += 1
	if parity % 2 == 0:
		return True
	else:
		return False
t = int(input())
for _ in range(t):
	s = list()
	d = collections.defaultdict(lambda : -1)
	q = int(input())
	c = -1
	e = 0
	o = 0
	for i in range(q):
		x = int(input())
		if d[x] != -1:
			print(e, o)
			continue
		s.append(x)
		d[x] = 1
		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(c + 1, len(s)):
			c = j
			if checkEvenParity(s[j]) == True:
				e += 1
			else:
				o += 1
		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


def binary_one_count(n):
	if n > 1:
		return n % 2 + binary_one_count(n // 2)
	return n
t = int(input())
for _ in range(t):
	mylist = [0] * 100001
	q = int(input())
	(even, odd, s) = (0, 0, set())
	for _ in range(q):
		x = int(input())
		if x not in s:
			for i in s.copy():
				s.add(i ^ x)
				if binary_one_count(i ^ x) % 2 == 0:
					even += 1
				else:
					odd += 1
			s.add(x)
			if binary_one_count(x) % 2 == 0:
				even += 1
			else:
				odd += 1
		print(even, odd)


for _ in range(int(input())):
	s = set()
	s1 = set()
	n = int(input())
	for i in range(n):
		e = int(input())
		if e not in s:
			for j in s:
				s1.add(e ^ j)
			s.add(e)
			s = s.union(s1)
			even = 0
			odd = 0
			for j in s:
				c = bin(j).count('1')
				if c % 2 == 0:
					even = even + 1
				else:
					odd = odd + 1
		print(even, odd)


for _ in range(int(input())):
	q = int(input())
	s = set()
	ex = set()
	e = 0
	o = 0
	for _ in range(q):
		x = int(input())
		if x in s:
			print(e, ' ', o)
			continue
		for j in s:
			if j != x:
				ex.add(x ^ j)
		s = s.union(ex)
		s.add(x)
		ex.clear()
		if e == 0 and o == 0:
			if str(bin(x)).count('1') % 2 == 1:
				o += 1
			else:
				e += 1
			print(e, ' ', o)
			continue
		if str(bin(x)).count('1') % 2 == 0:
			o = o + o
			e = e + e
			e += 1
		else:
			e1 = e + o
			o = o + e
			e = e1
			o += 1
		print(e, ' ', o)


def one(n):
	co = 0
	while n:
		co += n & 1
		n >>= 1
	return co

def xor(x, y):
	return (x | y) & (~x | ~y)
for t in range(int(input())):
	q = int(input())
	s = set()
	ev = od = 0
	while q > 0:
		n = int(input())
		if n not in s:
			co = one(n)
			if co % 2 == 0:
				ev += 1
			else:
				od += 1
			for i in list(s):
				new = xor(i, n)
				if new not in s:
					co = one(new)
					if co % 2 == 0:
						ev += 1
					else:
						od += 1
					s.add(new)
			s.add(n)
		print(ev, od)
		q -= 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
					elif 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
			elif countSetBits(c) % 2 == 0:
				count_even += 1
			else:
				count_odd += 1
		print(count_even, count_odd)
	a -= 1


arr = [True] * 100001
for i in range(1, 100001):
	if bin(i).count('1') % 2 == 1:
		arr[i] = False
for _ in range(int(input())):
	even = 0
	odd = 0
	s = set()
	for __ in range(int(input())):
		n = int(input())
		a = set()
		if n not in s:
			s.add(n)
			if arr[n]:
				(even, odd) = (2 * even + 1, 2 * odd)
			else:
				(even, odd) = (odd + even, odd + even + 1)
			for i in s:
				if i != n:
					d = i ^ n
					a.add(d)
			s = s.union(a)
		print(even, odd)


T = int(input())

def check(num):
	s1 = 0
	while num:
		num = num & num - 1
		s1 += 1
	return s1
for _ in range(T):
	s = set()
	num_even = 0
	num_odd = 0
	Q = int(input())
	while Q:
		X = int(input())
		if X in s:
			Q -= 1
			print(num_even, num_odd)
			continue
		s1 = set()
		for item in s:
			s1.add(item ^ X)
		for item in s1:
			s.add(item)
		par = check(X)
		if par % 2:
			(num_even, num_odd) = (num_even + num_odd, num_odd + num_even + 1)
		else:
			(num_even, num_odd) = (num_even + num_even + 1, num_odd + num_odd)
		print(num_even, num_odd)
		Q -= 1
		s.add(X)


def oddct(x):
	s = bin(x)[2:]
	if s.count('1') % 2 == 0:
		return False
	return True
for t in range(int(input())):
	s = set()
	q = int(input())
	e = 0
	o = 0
	for i in range(q):
		x = int(input())
		if x not in s:
			s1 = set()
			for y in s:
				q = x ^ y
				s1.add(q)
				if oddct(q) == 1:
					o += 1
				else:
					e += 1
			s.add(x)
			s = s | s1
			if oddct(x) == 1:
				o += 1
			else:
				e += 1
		else:
			pass
		print(e, o)


def parity(n):
	b = str(bin(n))
	p = b.count('1')
	if p % 2 != 0:
		return 0
	else:
		return 1
for i1 in range(0, int(input())):
	q = int(input())
	d = []
	count = 0
	way = 0
	p = dict()
	for i in range(0, q):
		n = int(input())
		p[n] = p.get(n, 0) + 1
		if p[n] == 1:
			if parity(n) == 1:
				count = count + 1
			else:
				way = way + 1
			d.append(n)
			for j in d[:-1]:
				b = j ^ n
				d.append(b)
				p[b] = p.get(b, 0) + 1
				if p[b] == 1:
					if parity(b) == 1:
						count = count + 1
					else:
						way = way + 1
		print(str(count) + ' ' + str(way))