Maximizing Identical Binary Strings After One Bit Flip

You are given (T) test cases. In each test case, you are given (M) binary strings. You are allowed to flip at most one bit (i.e. change a "0" to a "1" or vice versa) in each binary string in order to maximize the number of strings that become identical.

For a binary string (S = s_0s_1\dots s_{n-1}), flipping the bit at position (i) produces a new string: (S'i = s_0s_1\dots s{i-1}\overline{s_i}s_{i+1}\dots s_{n-1}), where (\overline{s_i}) denotes the flipped bit.

Your task is to determine, for each test case, the maximum number of binary strings that can be made identical after performing the allowed operation on the strings. If no flip is needed, the string can remain unchanged.

inputFormat

The input is read from standard input. The first line contains an integer (T), the number of test cases. For each test case, the first line contains an integer (M), the number of binary strings. The next line contains (M) binary strings separated by spaces.

outputFormat

For each test case, output a single line containing the maximum number of binary strings that can be made identical after performing at most one bit flip on each string.## sample

2
4
101 111 001 000
3
010 110 011

2
2