A palindrome is a string $t$ which reads the same backward as forward (formally, $t[i] = t[|t| + 1 - i]$ for all $i \in [1, |t|]$). Here $|t|$ denotes the length of a string $t$. For example, the strings 010, 1001 and 0 are palindromes.

You have $n$ binary strings $s_1, s_2, \dots, s_n$ (each $s_i$ consists of zeroes and/or ones). You can swap any pair of characters any number of times (possibly, zero). Characters can be either from the same string or from different strings — there are no restrictions.

Formally, in one move you:  choose four integer numbers $x, a, y, b$ such that $1 \le x, y \le n$ and $1 \le a \le |s_x|$ and $1 \le b \le |s_y|$ (where $x$ and $y$ are string indices and $a$ and $b$ are positions in strings $s_x$ and $s_y$ respectively),  swap (exchange) the characters $s_x[a]$ and $s_y[b]$. 

What is the maximum number of strings you can make palindromic simultaneously?


-----Input-----

The first line contains single integer $Q$ ($1 \le Q \le 50$) — the number of test cases.

The first line on each test case contains single integer $n$ ($1 \le n \le 50$) — the number of binary strings you have.

Next $n$ lines contains binary strings $s_1, s_2, \dots, s_n$ — one per line. It's guaranteed that $1 \le |s_i| \le 50$ and all strings constist of zeroes and/or ones.


-----Output-----

Print $Q$ integers — one per test case. The $i$-th integer should be the maximum number of palindromic strings you can achieve simultaneously performing zero or more swaps on strings from the $i$-th test case.


-----Example-----
Input
4
1
0
3
1110
100110
010101
2
11111
000001
2
001
11100111

Output
1
2
2
2



-----Note-----

In the first test case, $s_1$ is palindrome, so the answer is $1$.

In the second test case you can't make all three strings palindromic at the same time, but you can make any pair of strings palindromic. For example, let's make $s_1 = \text{0110}$, $s_2 = \text{111111}$ and $s_3 = \text{010000}$.

In the third test case we can make both strings palindromic. For example, $s_1 = \text{11011}$ and $s_2 = \text{100001}$.

In the last test case $s_2$ is palindrome and you can make $s_1$ palindrome, for example, by swapping $s_1[2]$ and $s_1[3]$.

Difficulty: interview

Starter code:

Solutions:
import sys
import math
from collections import defaultdict
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : list(map(int, input().split()))
def write(*args, sep="\n"):
  for i in args:
    sys.stdout.write("{}".format(i) + sep)
INF = float('inf')
MOD = int(1e9 + 7)

for _ in range(int(input())):
  n = int(input())
  arr = sorted([input() for i in range(n)], key=lambda x:len(x))

  zero_cnt, one_cnt = 0, 0
  for i in arr:
    zero_cnt += i.count('0')
    one_cnt += i.count('1')
  total = (zero_cnt//2) + (one_cnt//2)
  
  ans = 0

  for i in arr:
    if total >= len(i)//2:
      total -= len(i)//2 
      ans += 1
  
  print(ans)


from collections import Counter

for _ in range(int(input())):
    n = int(input())
    lens = []
    cnt = Counter()
    for _ in range(n):
        s = input()
        lens.append(len(s))
        cnt += Counter(s)
    pairs = 0
    singles = 0
    for v in list(cnt.values()):
        div, mod = divmod(v, 2)
        pairs += div
        singles += mod
    ans = 0
    lens.sort()
    for len_ in lens:
        div, mod = divmod(len_, 2)
        pairs -= div
        if mod:
            if singles:
                singles -= 1
            else:
                singles = 1
                pairs -= 1
        if pairs < 0:
            break
        ans += 1
    print(ans)


import sys
def I():
    return sys.stdin.readline().rstrip()

q = int( I() )
for _ in range( q ):
    n = int( I() )
    one, zero, odd = 0, 0, 0
    for _ in range( n ):
        s = I()
        odd += len( s ) & 1
        for c in s:
            if c == '0':
                zero += 1
            else:
                one += 1
    if ( one & 1 ) == 1 and ( zero & 1 ) == 1 and odd == 0:
        n -= 1
    print( n )


t=int(input())
for _ in range(t):
    n=int(input())
    it=[]
    co=0
    coo=0
    for i in range(n):
        a=input()
        co+=a.count("1")
        coo+=a.count("0")
        it.append([a.count("1"),a.count("0")])
    it.sort(key=lambda x:x[0]+x[1])
    ans=0
    for i in range(n):
        m=it[i][0]+it[i][1]
        if co==0 and coo==0:
            break
        if m%2==1:
            if co%2==1:
                co-=1
            elif coo%2==1:
                coo-=1
            m-=1
            st=True
            while m>0:
                if co>1:
                    co-=2
                    m-=2
                    continue
                if coo>1:
                    coo-=2
                    m-=2
                    continue
                st=False
                break
            if st:
                ans+=1
                continue
            else:
                break
        else:
            st=True
            while m>0:
                if co>1:
                    co-=2
                    m-=2
                    continue
                if coo>1:
                    coo-=2
                    m-=2
                    continue
                st=False
                break
            if st:
                ans+=1
                continue
            else:
                break
    print(ans)
                    
    


Q = int(input())
for _ in range(Q):
    N = int(input())
    X = []
    zeros = 0
    odds = 0
    for __ in range(N):
        s = input()
        odds += len(s) % 2
        zeros += s.count("0")
    
    if odds or (zeros % 2 == 0):
        print(N)
    else:
        print(N-1)


import sys
input = sys.stdin.readline

Q=int(input())

for test in range(Q):

    n=int(input())
    S=[input().strip() for i in range(n)]

    zero=0
    #ones=0
    lenflag=0

    for s in S:
        zero+=s.count("0")
        #ones+=s.count("1")

        if len(s)%2==1:
            lenflag=1

    if lenflag==1:
        print(n)
    else:
        if zero%2==0:
            print(n)
        else:
            print(n-1)

    


Q = int(input())
for _ in range(Q):
    n = int(input())
    zero, one = 0, 0
    odd = 0
    for _ in range(n):
        s = input()
        if len(s) % 2:
            odd = 1
        zero += s.count('0')
        one += s.count('1')

    if odd or zero % 2 == 0:
        print(n)
    else:
        print(n-1)

def sv():
	N = int(input())
	tot0 = 0
	allEven = True
	for n in range(N):
		s = input()
		if len(s) % 2: allEven = False
		tot0 += sum(1 for c in s if c == '0')
	print((N-1) if allEven and tot0 % 2 else N)
TC = int(input())
for tc in range(TC):
	sv()


import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))

def solve():
    n = getN()
    iso = False
    ise = False
    cnt1, cnt0 = 0, 0
    for _ in range(n):
        s = input().strip()
        if len(s) % 2 == 1:
            iso = 1
        else:
            ise = 1

        cnt = Counter(s)
        cnt1 += cnt["1"]
        cnt0 += cnt["0"]

    # print(iso, ise, cnt1, cnt0)
    if not iso and cnt1 % 2 and cnt0 % 2:
        print(n - 1)
    else:
        print(n)

def main():
    t = getN()
    for times in range(t):
        solve()


def __starting_point():
    main()
__starting_point()

q = int(input())

for _ in range(q):
    n = int(input())
    cnt = {'0': 0, '1': 0}
    even = []
    odd = []
    for _ in range(n):
        s = input()
        if len(s) & 1:
            odd.append(len(s))
        else:
            even.append(len(s))
        cnt['0'] += s.count('0')
        cnt['1'] += s.count('1')
    ans = n
    if cnt['0'] & 1 and cnt['1'] & 1 and len(odd) == 0:
        ans = n - 1
    print(ans)


q = int(input())
for _ in range(q):
    n = int(input())
    s = [input() for i in range(n)]
    cnt1 = 0
    cnt0 = 0
    cnt_odd = 0
    for i in range(n):
        if len(s[i]) % 2 == 1:
            cnt_odd += 1
        for j in range(len(s[i])):
            if s[i][j] == "1":
                cnt1 += 1
            else:
                cnt0 += 1
    
    if cnt_odd == 0:
        if cnt0 % 2 == 1 and cnt1 % 2 == 1:
            print(n-1)
        else:
            print(n)
    else:
        print(n)

for _ in range(int(input())):
	c0=0
	c1=0
	cods=0
	n=int(input())
	for y in range(n):
		s = input()
		zr=s.count('0')
		c0+=zr
		c1+=len(s)-zr
		cods += len(s)%2
	if c0%2+c1%2 <= cods:
		print(n)
	else:
		print(n-1)

import sys
from collections import deque
readline = sys.stdin.readline
q = int(readline())

for _ in range(q):
    n = int(readline())
    tmp = []
    ans = False
    c = 0
    for i in range(n):
        s = str(readline().split()[0])
        tmp.append(s)
        if len(s) % 2 == 1:
            ans = True
        for ss in s:
            if ss == '1':
                c+=1
    if ans or c % 2 == 0:
        print(n)
    else:
        print(n-1)


n = int(input())

while(n):
    
    n -= 1
    
    p = int(input())
    zeroes = 0
    ones = 0
    Lo = []
    Le = []
    for i in range(p):
        S = input()
        z = S.count('0')
        zeroes += z
        ones += len(S) - z
        if len(S) % 2:
            Lo.append(len(S))
        else:
            Le.append(len(S))
    Le.sort()
    Lo.sort()


    if zeroes % 2 == 0 and ones % 2 == 0:
        print(p)
    elif zeroes % 2 == 1 and ones % 2 == 1:
        if len(Lo) > 0:
            print(p)
        else:
            print(p - 1)
    else:
        print(p)


Q = int(input())
for _ in range(Q):
    n = int(input())
    zs = 0
    os = 0
    odd = 0
    for k in range(n):
        s = input()
        zs += s.count('0')
        os += s.count('1')
        odd += len(s) % 2
    #print(zs,os,odd)
    if zs % 2 == 1 and os % 2 == 1 and odd == 0:
        print(n-1)
    else:
        print(n)


q = int(input())
for i in range(q):
    amount = 0
    n = int(input())
    flag = 0
    for j in range(n):
        s = input()
        for k in range(len(s)):
            if s[k] == '1':
                amount += 1
        if len(s) % 2:
            flag = 1
   # print(flag, amount)
    if not flag and amount % 2:
        print(n - 1)
    else:
        print(n)


Q = int(input())
for q in range(Q):
    n = int(input())
    arr = [input() for i in range(n)]

    lens = [len(i) % 2 for i in arr]
    counts = [i.count('1') for i in arr]
    if sum(counts) % 2 == 0:
        print(n)
    else:
        if 1 in lens:
            print(n)
        else:
            print(n - 1)


#!/usr/bin/env python3
import sys

#lines = stdin.readlines()
def rint():
    return list(map(int, sys.stdin.readline().split()))

def input():
    return sys.stdin.readline().rstrip('\n')

def oint():
    return int(input())


q = oint()

for _ in range(q):
    n = oint()
    odd = 0
    ss = ''
    for _ in range(n):
        s = input()
        ss = ss + s
        if len(s)%2:
            odd = 1
    if odd:
        print(n)
    else:
        if ss.count('1')%2:
            print(n-1)
        else:
            print(n)


'''
Created on 2019. 9. 21.

@author: kkhh88
'''
#q = int(input())
#x, y = map(int,input().split(' '))

q = int(input())
for _ in range(q):
    n = int(input())
    l = [0] * n
    cnt0 = 0
    cnt1 = 0
    cntodd = 0
    
    for i in range(n):
        s = input()
        l[i] = len(s)
        if l[i] % 2 == 1:
            cntodd = cntodd + 1
        for c in s:
            if c == '0':
                cnt0 = cnt0 + 1
            else:
                cnt1 = cnt1 + 1
                
    if cnt0 % 2 == 1 and cntodd > 0:
        cnt0 = cnt0 - 1
        cntodd = cntodd - 1 
    if cnt1 % 2 == 1 and cntodd > 0:
        cnt1 = cnt1 - 1
        cntodd = cntodd - 1
        
    if cnt0 % 2 == 1 or cnt1 % 2 == 1:
        print(n - 1)
    else:
        print (n)


for _ in range(int(input())):
    n = int(input())
    s = [list(input()) for _ in range(n)]
    for elem in s:
        elem.sort()
    numberZeroes = 0
    numberOnes = 0
    numOdd = 0
    for elem in s:
        if (len(elem) % 2) == 1:
            numOdd += 1
        for num in elem:
            if num == "0":
                numberZeroes += 1
            else:
                numberOnes += 1

    while numOdd > 1:
        if numberOnes > 1:
            numberOnes -= 1
        else:
            numberZeroes -= 1
        numOdd -= 1

    if numOdd == 1:
        if numberOnes % 2 == 1:
            numberOnes -= 1
        elif numberZeroes % 2 == 1:
            numberZeroes -= 1
        elif numberOnes > 0:
            numberOnes -= 1
        else:
            numberZeroes -= 1

    if numberOnes % 2 == 0 and numberZeroes % 2 == 0:
        print(n)
    else:
        print(n-1)


from collections import *
from math import *
t = int(input())
for y in range(t):
    n = int(input())
    l = []
    for i in range(n):
        l.append(list(input()))
    ct = 0
    s = 0
    flag = 0
    for i in l:
        ct += i.count('1')
        s += len(i)
        if len(i) % 2 == 1:
            flag = 1
    if s%2 == 1:
        print(n)
    elif ct%2 == 0 or flag == 1:
        print(n)
    else:
        print(n-1)

for _ in range(int(input())):
    n = int(input())
    l = [input().strip() for i in range(n)]
    prob = 0
    odd = 0
    for i in range(n):
        z = l[i].count("0")
        o = l[i].count("1")
        if len(l[i]) % 2 == 1:
            odd = 1
            break
        else:
            if z % 2 == 1:
                prob += 1
    if odd == 1:
        print(n)
    else:
        if prob % 2 == 1:
            print(n-1)
        else:
            print(n)


for i in range(int(input())):
    n=int(input())
    cnt0,cnt1,cnt2=0,0,0
    for i in range(n):
        x=input()
        cnt2+=len(x)&1
        for i in x:
            if i=='0':
                cnt0+=1
            else:
                cnt1+=1
   # print(cnt0,cnt1,cnt2)
    if((cnt2-(cnt0&1)-(cnt1&1))%2==1) or (cnt0&1 and cnt1&1 and cnt2==0):
        print(n-1)
    else:
        print(n)

q = int(input())
for fwefe in range(q):
	n = int(input())
	j = 0
	z = 0
	par = []
	npar = []
	for i in range(n):
		s = input()
		je = s.count('1')
		ze = s.count('0')
		j += je
		z += ze
		if len(s) % 2 == 0:
			par.append(len(s))
		else:
			npar.append(len(s))
	par.sort()
	wyn = 0
	for i in par:
		if j < 0 or z < 0:
			break
		kz = 0
		while z - kz > j - (i - kz) and z - kz >= 0 and kz <= i:
			kz += 2
		z -= kz
		j -= (i-kz)
		wyn += 1
		if j < 0 or z < 0:
			wyn -= 1
	wyn += len(npar)
	print(wyn)
			
	


q = int(input())
while q:
    q -= 1
    n = int(input())
    a = 0
    b = 0
    c = 0
    for i in range(n):
        s = input()
        c1 = 0
        c2 = 0
        for i in s:
            if i == '1': c1 += 1
            else: c2 += 1
        if c1 % 2 and c2 % 2: a += 1
        elif c1 % 2 == 0 and c2 % 2 == 0: c += 1
        else: b += 1
    if a % 2 == 0: print(n)
    else:
        if b > 0: print(n)
        else: print(n - 1)