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.*;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Locale;


public class B1251 implements Runnable {
    public InputReader in;
    public PrintWriter out;

    public void solve() throws Exception {

        // solution goes here
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int N = in.nextInt();
            String[] strs = new String[N];
            for (int j = 0; j < N; j++) {
                strs[j] = in.nextLine();
            }
            /*
            00010 00100
            00111 01110
            001111
            z = 8
            o = 8


            odd  str = e & o || o & e
            even str = e & e

            for odd  : 1 if only 0 then 0 len = 2 - need to swap 1
            for even : 0 len=1 swap odd one

            0001
            11110
            00011
            11000
            10000
            01111 - odd always right
            only even can be wrong
            111000
            100000

             */
            int w = 0;
            int odd = 0;
            for (int i = 0; i < N; i++) {
                if (strs[i].length() % 2 == 0) {
                    int z = 0;
                    for (char ch : strs[i].toCharArray()) {
                        z += ch == '0' ? 1 : 0;
                    }
                    if (z % 2 == 0) {
                        continue;
                    }
                    w += w == 0 ? 1 : -1;
                    w += w > 0 && odd > 0 ? -1 : 0;
                } else {
                    odd++;
                    w += w > 0 ? -1 : 0;
                }
            }
            out.println(N - w);
        }
    }

    public void run() {
        try {
            in = new InputReader(System.in);
            out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
            Locale.setDefault(Locale.US);
            int tests = 1;
            while (tests-- > 0) {
                solve();
            }
            out.close();
        } catch (Throwable e) {
            e.printStackTrace();
            System.exit(7);
        }
    }

    static int abs(int x) {
        return x < 0 ? -x : x;
    }

    static int max(int a, int b) {
        return a > b ? a : b;
    }

    static int min(int a, int b) {
        return a < b ? a : b;
    }

    static long abs(long x) {
        return x < 0 ? -x : x;
    }

    static long max(long a, long b) {
        return a > b ? a : b;
    }

    static long min(long a, long b) {
        return a < b ? a : b;
    }

    public static void main(String[] args) {
        new Thread(null, new B1251(), "Main", 1 << 28).start();
    }

    static boolean OJ = System.getProperty("ONLINE_JUDGE") != null;

    public void console(Object... objects) {
        if (!OJ) {
            out.println(Arrays.deepToString(objects));
            out.flush();
        }
    }

    @SuppressWarnings({"Duplicates", "unused"})
    static class InputReader {

        private InputStream stream;
        private byte[] buf = new byte[2048];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader() {
            this.stream = System.in;
        }

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public InputReader(SpaceCharFilter filter) {
            this.stream = System.in;
            this.filter = filter;
        }

        public InputReader(InputStream stream, SpaceCharFilter filter) {
            this.stream = stream;
            this.filter = filter;
        }

        public int read() {
            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 char nextChar() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return (char) c;
        }

        public int nextDigit() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            return c - '0';
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            boolean negative = false;
            if (c == '-') {
                negative = true;
                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 negative ? -res : res;
        }

        public int[] nextInts(int N) {
            int[] nums = new int[N];
            for (int i = 0; i < N; i++)
                nums[i] = nextInt();
            return nums;
        }

        public long[] nextLongs(int N) {
            long[] nums = new long[N];
            for (int i = 0; i < N; i++)
                nums[i] = nextLong();
            return nums;
        }

        public int nextUnsignedInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res;
        }

        public final long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            boolean negative = false;
            if (c == '-') {
                negative = true;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return negative ? -res : res;
        }

        public final long nextUnsignedLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1 || c == '.'));

            if (c != '.') {
                return res * sgn;
            }
            c = read();

            long aft = 0;
            int len = 1;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                aft *= 10;
                len *= 10;
                aft += c - '0';
                c = read();
            } while (!isSpaceChar(c));

            return res * sgn + aft / (1.0 * len);
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndChar(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 boolean isEndChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            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 char[] nextChars() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            char[] chars = new char[res.length()];
            res.getChars(0, chars.length, chars, 0);
            return chars;
        }

        public int[][] nextIntMatrix(int rows, int cols) {
            int[][] matrix = new int[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        public long[][] nextLongMatrix(int rows, int cols) {
            long[][] matrix = new long[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextLong();
            return matrix;
        }

        public char[][] nextCharMap(int rows, int cols) {
            char[][] matrix = new char[rows][cols];
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    matrix[i][j] = nextChar();
            return matrix;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

}
