Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well. 

A competition with $N$ participants (numbered $1$ through $N$) is taking place in Chefland. There are $N-1$ rounds in the competition; in each round, two arbitrarily chosen contestants battle, one of them loses and drops out of the competition.

There are $10$ types of weapons (numbered $1$ through $10$). You are given $N$ strings $S_{1}, S_{2}, \ldots, S_{N}$; for each valid $i$ and $j$, the $j$-th character of $S_{i}$ is '1' if the $i$-th contestant initially has a weapon of type $j$ or '0' otherwise. During each battle, for each type $j$ such that both contestants in this battle currently have weapons of type $j$, these weapons of both contestants are destroyed; after the battle, the winner collects all remaining (not destroyed) weapons of the loser. Note that each contestant may win or lose regardless of the weapons he/she has.

Chef is feeling bored watching the contest, so he wants to find the maximum possible number of weapons the winner of the tournament could have after the last battle, regardless of which contestants fight in which battles or the results of the battles. Can you help him?

------  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$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains a single string $S_{i}$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum number of weapons the winner could have.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$|S_{i}| = 10$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ N ≤ 10$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

3

1110001101

1010101011

0000000011
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
Example case 1: If the first person defeats the second person, weapons $1$, $3$, $7$ and $10$ are destroyed. Then, if the third person defeats the first person (who now has weapons $2$, $5$, $8$ and $9$), weapons $9$ are destroyed and the winner has weapons $2$, $5$, $8$ and $10$.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

Mathematics


Solutions:
for i in range(int(input())):
	n = int(input())
	s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for i in range(n):
		a = list(input())
		for x in range(10):
			s[x] = s[x] ^ int(a[x])
	print(s.count(1))


tests = int(input())

def xor(lst):
	lst_c = []
	i = 0
	while i < 10:
		x = 0
		for ele in lst:
			x = x ^ int(ele[i])
		lst_c.append(x)
		i += 1
	return lst_c.count(1)
for i in range(tests):
	N = int(input())
	L = []
	for i in range(N):
		L.append(input())
	c = xor(L)
	print(c)


from os import path
import sys
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	a = [0] * 10
	mx = 0
	for i in range(n):
		s = str(input())
		for i in range(10):
			if s[i] == '1':
				a[i] += 1
	for i in range(10):
		if a[i] & 1:
			mx += 1
	print(mx)


for _ in range(int(input())):
	N = int(input())
	S = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for i in range(N):
		a = list(input())
		for x in range(10):
			S[x] = S[x] ^ int(a[x])
	print(S.count(1))


for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(input())
	if n == 1:
		print(l[0].count('1'))
	else:
		a = int(l[0], 2)
		b = int(l[1], 2)
		temp = a ^ b
		for i in range(2, n):
			t = int(l[i], 2)
			temp = temp ^ t
		temp = bin(temp)
		print(temp.count('1'))


for _ in range(int(input())):
	n = int(input())
	a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for i in range(n):
		l = list(input())
		for i in range(10):
			a[i] = a[i] ^ int(l[i])
	print(a.count(1))


for _ in range(int(input())):
	n = int(input())
	s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for i in range(n):
		l = list(input())
		for j in range(10):
			s[j] = s[j] ^ int(l[j])
	print(s.count(1))


for _ in range(int(input())):
	n = int(input())
	temp = [0] * 10
	for i in range(n):
		s = input()
		for i in range(10):
			temp[i] = temp[i] ^ int(s[i])
	print(temp.count(1))


for _ in range(int(input())):
	Number = int(input())
	Sub = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for i in range(Number):
		mk = list(input())
		for x in range(10):
			Sub[x] = Sub[x] ^ int(mk[x])
	print(Sub.count(1))


for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		a = input()
		l.append(a)
	w = []
	for i in range(10):
		count = 0
		for j in range(n):
			b = l[j]
			if b[i] == '1':
				count += 1
		if count % 2 == 0:
			w.append(0)
		else:
			w.append(1)
	weapons = 0
	for i in w:
		if i == 1:
			weapons += 1
	print(weapons)


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	c = 0
	k = 0
	for __ in range(n):
		s = input()
		l.append(s)
	for i in range(10):
		for j in range(n):
			k = k ^ int(l[j][i])
		if k == 1:
			c += 1
		k = 0
	print(c)


def fight(s1, s2):
	new_s = ''
	for i in range(len(s1)):
		if s1[i] == s2[i]:
			new_s += '0'
		else:
			new_s += '1'
	return new_s
for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(n - 1):
		sn = input()
		s = fight(s, sn)
	print(s.count('1'))
	count = 0


t = int(input())
while t > 0:
	n = int(input())
	x = 0
	for i in range(n):
		y = int(input(), 2)
		x = x ^ y
	count = 0
	while x != 0:
		x = x & x - 1
		count += 1
	print(count)
	t -= 1


import numpy as np
for _ in range(int(input())):
	n = int(input())
	a = []
	for _ in range(n):
		s = bin(int(input(), 2))
		a.append(int(s, 2))
	k = np.bitwise_xor.reduce(a)
	l = bin(k)
	print(l.count('1'))


t = int(input())
for i in range(t):
	n = int(input())
	s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for j in range(n):
		a = list(input())
		for k in range(10):
			s[k] = s[k] ^ int(a[k])
	print(s.count(1))


def getlist():
	return list(input())

def main():
	for _ in range(int(input())):
		s = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
		for i in range(int(input())):
			s1 = getlist()
			for j in range(10):
				s[j] = s[j] ^ int(s1[j])
		print(s.count(1))
main()


tsp = int(input())
for m in range(tsp):
	s = []
	np = int(input())
	for jps in range(np):
		s.append(int(input(), 2))
	ans = 0
	for number in s:
		ans = ans ^ number
	print('{0:b}'.format(ans).count('1'))


for i in range(int(input())):
	s = 0
	n = int(input())
	for j in range(n):
		s1 = int('0b' + input(), 2)
		s = s ^ s1
	s = bin(s)[2:]
	print(s.count('1'))


t = int(input())
for i in range(t):
	n = int(input())
	lst = []
	for i in range(n):
		s = input()
		lst.append(s)
	countss = 0
	for i in range(len(s)):
		counts = 0
		for j in range(n):
			if lst[j][i] == '1':
				counts = counts + 1
		if counts % 2 == 1:
			countss = countss + 1
	print(countss)


while True:
	try:
		t = int(input())
	except:
		break
	for _ in range(t):
		n = int(input())
		weapon_not_destroyed = [0] * 10
		count = 0
		for i in range(1, n + 1):
			s = input()
			arr = [int(j) for j in s]
			for j in range(10):
				weapon_not_destroyed[j] ^= arr[j]
		for i in range(10):
			if weapon_not_destroyed[i] == 1:
				count += 1
		print(count)


for i in range(int(input())):
	n = int(input())
	lt = []
	for i in range(n):
		s = input()
		lt.append(s)
	a = lt[0]
	for j in range(1, len(lt)):
		b = lt[j]
		for i in range(len(a)):
			if a[i] == b[i]:
				s = list(a)
				s[i] = '0'
				a = ''.join(s)
			else:
				s = list(a)
				s[i] = '1'
				a = ''.join(s)
	print(a.count('1'))


t = int(input())
while t > 0:
	n = int(input())
	S = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for i in range(n):
		a = list(input())
		for x in range(10):
			S[x] = S[x] ^ int(a[x])
	print(S.count(1))
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = []
	s = 0
	for i in range(n):
		l.append(int(input(), 2))
	for i in l:
		s ^= i
	d = format(s, 'b')
	print(d.count('1'))


def converter(string):
	n = 0
	for i in range(len(string)):
		n += 2 ** i * int(string[i])
	return n
for t in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(converter(input()))
	ans = arr[0]
	arr.remove(ans)
	for item in arr:
		ans ^= item
	num = 0
	ans = bin(ans).replace('0b', '')
	for bit in ans:
		if bit == '1':
			num += 1
	print(num)


T = int(input())
for i in range(T):
	N = int(input())
	L = []
	for i in range(N):
		a = input()
		L.append(a)
	c = 0
	for j in range(10):
		n = 0
		for i in range(N):
			n += int(L[i][j])
		if n % 2 != 0:
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	x = [0] * 10
	for i in range(n):
		n = list(input())
		for j in range(10):
			x[j] = x[j] ^ int(n[j])
	print(x.count(1))


for _i in range(int(input())):
	n = int(input())
	w = [0] * 10
	for u in range(0, n):
		Q = list(input())
		for t in range(0, 10):
			w[t] = w[t] ^ int(Q[t])
	print(w.count(1))


for _ in range(int(input())):
	a = int(input())
	b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for i in range(a):
		n = list(input())
		for x in range(10):
			b[x] = b[x] ^ int(n[x])
	print(b.count(1))


for i in range(int(input())):
	n = int(input())
	l1 = [0] * 10
	for i in range(n):
		l = list(input())
		for j in range(10):
			l1[j] = l1[j] ^ int(l[j])
	print(l1.count(1))


for i in range(int(input())):
	n = int(input())
	s = 0
	for i in range(n):
		s = s ^ int(input(), 2)
	print(str(bin(s)).count('1'))


for i in range(int(input())):
	p = int(input())
	l = []
	c1 = 0
	for j in range(p):
		n = list(input())
		l.append(n)
	for i in range(10):
		c = 0
		for j in range(p):
			if l[j][i] == '1':
				c += 1
		if c % 2 != 0:
			c1 += 1
	print(c1)


for _ in range(int(input())):
	n = int(input())
	s = [int(input(), 2) for _ in range(n)]
	result = s[0]
	[(result := (result ^ value)) for value in s[1:]]
	result = bin(result).count('1')
	print(result)


for _ in range(int(input())):
	N = int(input())
	res = 0
	for i in range(N):
		num = int(input(), 2)
		res ^= num
	res = '{0:b}'.format(res)
	print(res.count('1'))


for _ in range(int(input())):
	n = int(input())
	S = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for r in range(n):
		a = list(input())
		for x in range(10):
			S[x] = S[x] ^ int(a[x])
	print(S.count(1))


for _ in range(int(input())):
	n = int(input())
	p = [0] * 10
	for i in range(n):
		t = input()
		for j in range(len(t)):
			p[j] = p[j] ^ int(t[j])
	print(p.count(1))


t = int(input())
for _ in range(t):
	n = int(input())
	d = {}
	for i in range(n):
		l = list(input())
		for j in range(len(l)):
			if l[j] == '1':
				d[j] = d.get(j, 0) + 1
	cnt = 0
	for i in d.values():
		if i % 2 != 0:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	l = []
	for a in range(n):
		l.append(input())
	new_str = '0000000000'
	temp_str = ''
	for i in l:
		for j in range(10):
			if i[j] != new_str[j]:
				temp_str += '1'
			else:
				temp_str += '0'
		(new_str, temp_str) = (temp_str, '')
	print(new_str.count('1'))


T = int(input())
for i in range(T):
	N = int(input())
	S = int(input(), 2)
	for i in range(0, N - 1):
		A = int(input(), 2)
		S ^= A
	S = bin(S)
	print(S.count('1'))


for _ in range(int(input())):
	N = int(input())
	S = []
	S.append(int(input(), 2))
	for i in range(0, N - 1):
		A = int(input(), 2)
		B = S.pop(0)
		S.append(A ^ B)
	A = bin(S.pop(0))
	print(A.count('1'))


for _ in range(int(input())):
	n = int(input())
	list1 = []
	sum = []
	sum1 = 0
	for x in range(n):
		list1.append(input())
	for x in list1[0]:
		sum.append(int(x))
	for x in range(1, n):
		for j in range(len(list1[x])):
			sum[j] = sum[j] + int(list1[x][j])
	for x in range(len(sum)):
		if sum[x] % 2 != 0:
			sum1 += 1
	print(sum1)


tc = int(input())
for _ in range(tc):
	person = int(input())
	wepon = []
	for k in range(person):
		st = input()
		lis = [int(x) for x in st]
		wepon.append(lis)
	if person == 1:
		print(wepon[0].count(1))
	else:
		for i in range(person - 1):
			a = 0
			b = 0
			for j in range(10):
				if wepon[i][j] == 1 and wepon[i + 1][j] == 0:
					wepon[i + 1][j] = 1
				elif wepon[i][j] == 0 and wepon[i + 1][j] == 1:
					wepon[i + 1][j] = 1
				else:
					wepon[i + 1][j] = 0
		print(wepon[person - 1].count(1))


for t in range(int(input())):
	n = int(input())
	value = 0
	for char in range(n):
		string = int(input(), 2)
		value ^= string
	print(bin(value).count('1'))


def weapon(string):
	ans = 0
	for ch in range(10):
		if string[9 - ch] == '1':
			ans += 2 ** ch
	return ans
for t in range(int(input())):
	n = int(input())
	value = 0
	for char in range(n):
		string = input()
		result = weapon(str(string))
		value ^= result
	print(bin(value).count('1'))


for test in range(int(input())):
	n = int(input())
	total = [0] * 10
	for i in range(n):
		j = input()
		for i in range(10):
			if j[i] == '1':
				total[i] += 1
	count = 0
	for i in range(10):
		if total[i] % 2 == 1:
			count += 1
	print(count)


testcases = int(input())
for _ in range(testcases):
	n = int(input())
	games = []
	for __ in range(n):
		string = input()
		games.append(string)
	nums = 0
	for i in range(10):
		count = 0
		for j in range(n):
			if games[j][i] == '1':
				count += 1
		if count % 2 == 1:
			nums += 1
	print(nums)


def xor(s1, s2):
	nstr = len(s1)
	s = ''
	for i in range(nstr):
		bit = int(s1[i]) ^ int(s2[i])
		s = s + str(bit)
	return s

def sum_digit(str1):
	ndigit = 0
	for x in str1:
		ndigit += int(x)
	return ndigit
T = int(input())
for i in range(T):
	n = int(input())
	s0 = ['' for i in range(n)]
	inpOk = 1
	for i in range(n):
		s0[i] = input()
		slen = len(s0[i])
		if slen != 10:
			inpOk = 0
			print('Wrong value of String Length =', slen, '... should be 10')
			exit
	if inpOk:
		s1 = s0[0]
		for i in range(1, n):
			s2 = s0[i]
			s1 = xor(s1, s2)
		ndigit = sum_digit(s1)
		print(ndigit)


def xor(s1, s2):
	nstr = len(s1)
	s = ''
	for i in range(nstr):
		bit = int(s1[i]) ^ int(s2[i])
		s = s + str(bit)
	return s

def sum_digit(str1):
	ndigit = 0
	for x in str1:
		ndigit += int(x)
	return ndigit
T = int(input())
for i in range(T):
	n = int(input())
	s0 = ['' for i in range(n)]
	for i in range(n):
		s0[i] = input()
	s1 = s0[0]
	for i in range(1, n):
		s2 = s0[i]
		s1 = xor(s1, s2)
	ndigit = sum_digit(s1)
	print(ndigit)