#P1251B. Binary Palindromes

Binary Palindromes

Description

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

You have nn binary strings s1,s2,,sns_1, s_2, \dots, s_n (each sis_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,bx, a, y, b such that 1x,yn1 \le x, y \le n and 1asx1 \le a \le |s_x| and 1bsy1 \le b \le |s_y| (where xx and yy are string indices and aa and bb are positions in strings sxs_x and sys_y respectively),
  • swap (exchange) the characters sx[a]s_x[a] and sy[b]s_y[b].

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

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

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

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

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

Input

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

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

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

Output

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

Samples

样例输入 1

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

样例输出 1

1
2
2
2

Note

In the first test case, s1s_1 is palindrome, so the answer is 11.

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 s1=0110s_1 = \text{0110}, s2=111111s_2 = \text{111111} and s3=010000s_3 = \text{010000}.

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

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