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].
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.*;
import java.io.*;
import java.math.*;
public class Main6{

/*static class Pair
    { 
        String x;
		int y;
        public Pair(String x, int y) 
        {     
            this.x=x;
			this.y=y;
        }     
        
    @Override
            public int hashCode() 
            { 
                final int temp = 14; 
                int ans = 1; 
                ans =x*31+y*13; 
                return ans; 
            } 
      
            // Equal objects must produce the same 
            // hash code as long as they are equal 
        @Override
        public boolean equals(Object o) 
        { 
            if (this == o) { 
                return true; 
            } 
            if (o == null) { 
                return false; 
            } 
            if (this.getClass() != o.getClass()) { 
                return false; 
            } 
            Pair other = (Pair)o; 
            if (this.x != other.x || this.y!=other.y) { 
                return false; 
            } 
            return true; 
        } 
            
    } 
    static class Pair1
    {
        String x;
        int y;
        int z;
        
    }
    static class Compare
    { 
        static void compare(Pair arr[], int n) 
        { 
            // Comparator to sort the pair according to second element 
            Arrays.sort(arr, new Comparator<Pair>() { 
                @Override public int compare(Pair p1, Pair p2) 
                { 
                    if(p1.x>p2.x)
                    {
                        return 1;
                    }
                    else if(p1.x<p2.x)
                    {
                        return -1;
                    }
                    else
                    {
                        if(p1.y>p2.y)
						{
							return 1;
						}
						else if(p1.y<p2.y)
						{
							return -1;
						}
						else
						{
							if(p1.z>p2.z)
							{
								return 1;
							}
							else if(p1.z<p2.z)
							{
								return -1;
							}
							else
								return 0;
						}
                    }
                } 
            }); 
        }
        
    }
    
    */
    public static long pow(long a, long b)
    {
        long result=1;
        while(b>0)
        {
            if (b % 2 != 0)
            {
                result=(result*a)%1000000007;
                b--;
            } 
            a=(a*a)%1000000007;
            b /= 2;
        }   
        return result;
    }
    public static long fact(long num)
    {
                long value=1;
                int i=0;
                for(i=2;i<num;i++)
                {
                    value=((value%mod)*i%mod)%mod;
                }
                return value;
            }
            public static long gcd(long a, long b)
            {
                if (a == 0)
                    return b;
                return gcd(b%a, a);
            }
            
    /*        public static long lcm(long a,long b)
            {
                return a * (b / gcd(a, b));
            }
        */    public static long sum(int h)
            {
                return (h*(h+1)/2);
            }
        /*   public static void dfs(int parent,boolean[] visited,int[] dp)
            {
                ArrayList<Integer> arr=new ArrayList<Integer>();
                arr=graph.get(parent);
                visited[parent]=true;
                for(int i=0;i<arr.size();i++)
                {
                    int num=(int)arr.get(i);
                    if(visited[num]==false)
                    {
                        dfs(num,visited,dp);
                    }
                    dp[parent]=Math.max(dp[num]+1,dp[parent]);
                }
            }
        //    static int flag1=0;
            static int[] dis;*/
            static int mod=1000000007;
            static ArrayList<ArrayList<Integer>> graph;
            static ArrayList<ArrayList<Integer>> g;
            
       /*    public static void bfs(int num,int size)
            {
                boolean[] visited=new boolean[size+1];
                Queue<Integer> q=new LinkedList<>();
                q.add(num);
                ans[num]=1;
                visited[num]=true;
                while(!q.isEmpty())
                {
                    int x=q.poll();
                    ArrayList<Integer> al=graph.get(x);
                    for(int i=0;i<al.size();i++)
                    {
                        int y=al.get(i);    
                        if(visited[y]==false)
                        {
                            q.add(y);
                            ans[y]=ans[x]+1;
                            visited[y]=true;
                        }
                    }
                }
            }
            static int[] ans;*/
            
            
            
            
            
            
            
            
            
        //    static int[] a;              
            public static int[] sort(int[] a)
            {
                int n=a.length;
                ArrayList<Integer> ar=new ArrayList<>();
                for(int i=0;i<a.length;i++)
                {
                    ar.add(a[i]);
                }
                Collections.sort(ar);
                for(int i=0;i<n;i++)
                {
                    a[i]=ar.get(i);
                }
                return a;
            }
	/*		static class pqcomparator implements Comparator<Pair>
			{
				public int compare(Pair p1 ,Pair p2)
				{
					if(p1.y>p2.y)
					{
						return -1;
					}
					else
						return 1;
				}
			}
		*/	public static void dfs(int parent,boolean[] visited)
            {
                ArrayList<Integer> arr=new ArrayList<Integer>();
                arr=graph.get(parent);
                visited[parent]=true;
				ar.add(parent);
				count++;
				for(int i=0;i<arr.size();i++)
                {
					int num=(int)arr.get(i);
                    if(visited[num]==false)
                    {
						dfs(num,visited);
                    }
            	 }
            }
			static int count=0;
			static ArrayList<Integer> ar;
			static public void main(String args[])throws IOException
            {
				int t=i();
				StringBuilder sb=new StringBuilder();
				while(t-->0)
				{
					int n=i();
					String[] s=new String[n];
					int[] count=new int[2];
					ArrayList<Integer> ar=new ArrayList<>();
				//	Pair[] pair=new Pair[n];
					for(int i=0;i<n;i++)
					{
						s[i]=s();
				//		pair[i]=new Pair(s[i],s[i].length());
						ar.add(s[i].length());
						for(int j=0;j<s[i].length();j++)
						{
							count[s[i].charAt(j)-'0']++;
						}
					}
					Collections.sort(ar);
					int ans=0;
					for(int i=0;i<n;i++)
					{
						if(ar.get(i)%2!=0)
						{
							int flag=0;
						//	pln((ar.get(i)/2+1)+" "+count[0]+" "+count[1]);
							for(int j=0;j<=ar.get(i)/2;j++)
							{
								if(j==ar.get(i)/2)
								{
									if(count[0]%2==1)
									{
										count[0]--;
									}
									else if(count[1]%2==1)
									{
										count[1]--;
									}
									else if(count[0]>0)
									{
										count[0]--;
									}
									else if(count[1]>0)
										count[1]--;
									else
										flag=1;
								}
								else
								{
									if(count[0]>=2)
										count[0]-=2;
									else if(count[1]>=2)
										count[1]-=2;
									else
									{
										flag=1;
									}
								}
							}
							if(flag==0)
								ans++;
						}
						else
						{
							int flag=0;
							for(int j=0;j<ar.get(i)/2;j++)
							{
								if(count[0]>=2)
									count[0]-=2;
								else if(count[1]>=2)
									count[1]-=2;
								else
								{
									flag=1;
								}
							}
							if(flag==0)
								ans++;
						}
					}
					
					sb.append(ans+"\n");
				}
				System.out.print(sb.toString());
			}
			static boolean areParenthesisBalanced(char exp[]) 
			{ 
			   Stack<Character> st=new Stack<>();
			   for(int i=0;i<exp.length;i++) 
			   { 
					if (exp[i] == '(') 
						st.push(exp[i]); 
					if (exp[i] == ')') 
					{ 
						if (st.isEmpty()) 
						{ 
						   return false; 
						}  
						else if ( !isMatchingPair(st.pop(), exp[i]) ) 
						{ 
						   return false; 
						} 
					} 
					
				} 
				if (st.isEmpty()) 
					return true; 
				else
				 { 
					 return false; 
				 }  
			}  
			static boolean isMatchingPair(char character1, char character2) 
			{ 
			   if (character1 == '(' && character2 == ')') 
				 return true; 
			   else
				 return false; 
			} 
            /**/
            static InputReader in=new InputReader(System.in);
                static OutputWriter out=new OutputWriter(System.out);
                public static long l()
                {
                    String s=in.String();
                    return Long.parseLong(s);
                }
                public static void pln(String value)
                {
                    System.out.println(value);
                }
                public static int i()
                {
                    return in.Int();
                }
                public static String s()
                {
                    return in.String();
                }
    }
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
        class InputReader {
             
            private InputStream stream;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;
            private SpaceCharFilter filter;
         
            public InputReader(InputStream stream) {
                this.stream = stream;
            }
         
            public int read() {
                if (numChars== -1)
                    throw new InputMismatchException();
                if (curChar >= numChars) {
                    curChar = 0;
                    try {
                        numChars = stream.read(buf);
                    } catch (IOException e) {
                        throw new InputMismatchException();
                    }
                    if (numChars <= 0)
                        return -1;
                }
                return buf[curChar++];
            }
         
            public int Int() {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
         
            public String String() {
                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 boolean isSpaceChar(int c) {
                if (filter != null)
                    return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }
         
            public String next() {
                return String();
            }
         
            public interface SpaceCharFilter {
                public boolean isSpaceChar(int ch);
            }
        }
         
        class OutputWriter {
            private final PrintWriter writer;
         
            public OutputWriter(OutputStream outputStream) {
                writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
            }
         
            public OutputWriter(Writer writer) {
                this.writer = new PrintWriter(writer);
            }
         
            public void print(Object...objects) {
                for (int i = 0; i < objects.length; i++) {
                    if (i != 0)
                        writer.print(' ');
                    writer.print(objects[i]);
                }
            }
         
            public void printLine(Object...objects) {
                print(objects);
                writer.println();
            }
         
            public void close() {
                writer.close();
            }
         
            public void flush() {
                writer.flush();
            }
         
            }
         
            class IOUtils {
         
            public static int[] readIntArray(InputReader in, int size) {
                int[] array = new int[size];
                for (int i = 0; i < size; i++)
                    array[i] = in.Int();
                return array;
            }
         
            } 

