Maximum Rows with All Ones

You are given a binary matrix and you are allowed to flip columns any number of times. A flip operation on a column \(j\) will transform every element \(a_{i,j}\) of the matrix into \(1 - a_{i,j}\). The objective is to select a set of column flips so that the maximum number of rows become all ones. In other words, find the maximum number of rows that can be converted into a row consisting entirely of ones (i.e., \(1\)'s).

Input Format: The input starts with an integer \(t\), the number of test cases. For each test case, the first line contains an integer \(n\) denoting the number of rows (and columns) of the matrix. This is followed by \(n\) lines each containing \(n\) space-separated binary digits (\(0\) or \(1\)).

Output Format: For each test case, print a single integer on a new line --- the maximum number of rows that can become all ones after performing any number of column flip operations.

inputFormat

The first line of the input contains a single integer \(t\) representing the number of test cases. For each test case, the first line contains an integer \(n\) (the size of the matrix). This is followed by \(n\) lines, each with \(n\) space-separated integers (either 0 or 1) representing the rows of the matrix.

outputFormat

For each test case, output a single line containing one integer: the maximum number of rows that can be made to consist entirely of 1's after any sequence of column flip operations.

## sample

5
3
1 0 1
0 1 0
1 1 1
2
0 0
1 1
2
0 1
0 1
3
1 0 1
0 1 1
1 1 0
1
0

2
2
2
1
1

</p>