#P1251B. Binary Palindromes
Binary Palindromes
Description
A palindrome is a string which reads the same backward as forward (formally, for all ). Here denotes the length of a string . For example, the strings 010, 1001 and 0 are palindromes.
You have binary strings (each 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 such that and and (where and are string indices and and are positions in strings and respectively),
- swap (exchange) the characters and .
What is the maximum number of strings you can make palindromic simultaneously?
The first line contains single integer () — the number of test cases.
The first line on each test case contains single integer () — the number of binary strings you have.
Next lines contains binary strings — one per line. It's guaranteed that and all strings constist of zeroes and/or ones.
Print integers — one per test case. The -th integer should be the maximum number of palindromic strings you can achieve simultaneously performing zero or more swaps on strings from the -th test case.
Input
The first line contains single integer () — the number of test cases.
The first line on each test case contains single integer () — the number of binary strings you have.
Next lines contains binary strings — one per line. It's guaranteed that and all strings constist of zeroes and/or ones.
Output
Print integers — one per test case. The -th integer should be the maximum number of palindromic strings you can achieve simultaneously performing zero or more swaps on strings from the -th test case.
Samples
Note
In the first test case, is palindrome, so the answer is .
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 , and .
In the third test case we can make both strings palindromic. For example, and .
In the last test case is palindrome and you can make palindrome, for example, by swapping and .