A palindrome is a string t which reads the same backward as forward (formally, t[i] = t[|t| + 1 - i] for all i ∈ [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, ..., 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 ≤ x, y ≤ n and 1 ≤ a ≤ |s_x| and 1 ≤ b ≤ |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 ≤ Q ≤ 50) — the number of test cases.

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

Next n lines contains binary strings s_1, s_2, ..., s_n — one per line. It's guaranteed that 1 ≤ |s_i| ≤ 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 = 0110, s_2 = 111111 and s_3 = 010000.

In the third test case we can make both strings palindromic. For example, s_1 = 11011 and s_2 = 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].
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package solution;

/**
 *
 * @author USER
 */

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class Solution{     
    
    
   
    public static void main(String [] args){
        //InputReader sc=new InputReader(System.in);
        Scanner sc=new Scanner(System.in);
       // BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
               //    Scanner sc=new Scanner(System.in);
        //BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        
        int t=sc.nextInt();
        while(t-->0){
            int n=sc.nextInt();
            int zr=0;
            int one=0;
            int even=0;
            int odd=0;
            int[]a=new int[n];
            for(int j=0;j<n;j++){
                String s=sc.next();
                a[j]=s.length();
                if(a[j]%2==1)odd++;
                //else odd++;
            
                
                for(int i=0;i<s.length();i++){
                    if(s.charAt(i)=='0'){
                        zr++;
                    }
                    else one++;
                }
            }
                int count=n-1;
               // Arrays.sort(a);
                
            if(zr%2==0&&one%2==0){
                if(odd%2==0){
                    count=n;
                }
            }
            else if(zr%2==1&&one%2==1){
                if(odd!=0){
                    count=n;
                }
            }
            else{
                if(odd%2==1){
                    count=n;
                }
            }
                
                    
                
                
            
            System.out.println(count);
           
          
          
          
          
          
            }
        w.close();
    

    }
    static class InputReader { 
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        public InputReader(InputStream st) {
            this.stream = st;
        } 
        public int read() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } 
                catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
        public int ni() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        } 
        public long nl() {
            int c = read();
            while (isSpaceChar(c)) {
            c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        } 
        public int[] nia(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        } 
        public String rs() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                    c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        } 
        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        } 
    }
    public static class Key {

        private final int x;
        private final int y;

        public Key(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Key)) return false;
            Key key = (Key) o;
            return x == key.x && y == key.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }

    }
    
    static PrintWriter w = new PrintWriter(System.out);
    static long mod=998244353L,mod1=1000000007;
    static int co[][];
    static void dsort(){
        Arrays.parallelSort(co,(o1,o2)->o1[0]!=o2[0]?o1[0]-o2[0]:o1[1]-o2[1]);
    }
     static long  power(long x, long y) { 
        long temp=0; 
        if( y == 0) 
            return 1; 
        temp = power(x, y/2); 
        if (y%2 == 0) 
            return (temp*temp)%mod1; 
        else
            return (((x*temp)%mod1)*temp)%mod1; 
    } 
    static long modInverse(long a, long m){
        long num=m;
        long x=1;
        long power=a%mod1;
        while(num>0){
              if(num%2==1){
                  x=(x*power)%mod1;
            }
            num>>=1;
            power=(power*power)%mod1;         
        }
        return x;
    }
    static long ncrWithoutMod(int n,int r){
        if(n<r)return 0L;
        long ans=fact[n]/(fact[r]*fact[n-r]);
        return ans;
    }
    static long fact[]=new long[1000005];
    public static void findFact(){
        fact[0]=1;
        for(int i=1;i<=1000000;i++){
            fact[i]=(i*fact[i-1])%mod1;
        }
    }
    

                
 
class MySort {
    
    public void mergeSort(int []a,int left,int right){
        if(left<right){
            int m=(left+right)/2;
            mergeSort(a, left, m);
            mergeSort(a, m+1, right);
            merging(a,left,m,right);
            
        }
        
        
    }
    private void merging(int[]a,int left,int m,int right){
        int n1=m-left+1;
        int n2=right-(m+1)+1;
        int []L=new int[n1];
        int []R=new int[n2];
        
        for(int i=0;i<n1;i++){L[i]=a[left+i];}
        for(int i=0;i<n2;i++){R[i]=a[m+1+i];}
        
        int i=0;int j=0;
        int k=left;
        while(i<n1&&j<n2){
            if(L[i]<=R[j]){
                a[k]=L[i];
                i++;
            }
            else {
                a[k]=R[j];
                j++;
            }
            k++;
        }
        
        while(i<n1){
            a[k]=L[i];
            i++;
            k++;
        }
        while(j<n2){
            a[k]=R[j];
            j++;
            k++;
        }
    }
    
}
}

                
