JYY has recently become obsessed with jigsaw puzzles. As a computer scientist, JYY has a set of black and white puzzle pieces, and he hopes to arrange them in a reasonable way so that the final pattern contains the largest possible all-white sub-rectangle.

JYY has a total of $S$ puzzle pieces, numbered from 1 to $S$. The puzzle piece numbered $i$ is a grid rectangle of $N$ rows and $W_i$ columns, where each cell is either black or white.

Initially, JYY places his $S$ puzzle pieces on the table in order of their numbers, connected side-by-side to form a large rectangle of $N$ rows and $M$ columns (where $M = \sum_{i=1}^{S} W_i$).

Later, JYY discovers that he can change the connection order of these $S$ puzzle pieces to increase the area of the largest all-white sub-rectangle in the resulting $N \times M$ large rectangle.

Now, JYY wants to know how to arrange them to obtain the largest all-white sub-rectangle. Please help him calculate the best arrangement.

Input

The input contains multiple test cases. The first line of the input file contains an integer $T$, representing the number of test cases. The test cases follow in order.

The first line of each test case contains two integers $S$ and $N$.

Then follow $S$ blocks of input, where the $i$-th block corresponds to the puzzle piece numbered $i$.

In the $i$-th block: The first line contains an integer $W_i$. The next $N$ lines describe an $N \times W_i$ grid of 0s and 1s. A 0 at row $x$ and column $y$ indicates that the cell in the puzzle piece is white, while a 1 indicates that it is black.

Output

For each test case, output a single line containing an integer $ans$, representing the maximum possible area of an all-white sub-rectangle.

Examples

Input 1

1
3 4
4
1001
0000
0010
1001
3
000
010
000
011
2
00
10
01
00

Output 1

6

Note

The large rectangle formed by the optimal arrangement is:

000100100
010000010
000001001
011100100

The bolded part is the white sub-rectangle with an area of 6.

Constraints

• For 10% of the data: $S = 1, N \le 30, W_i \le 30$;
• For 30% of the data: $S \le 3$;
• For 50% of the data: $S \le 1000$;
• For 100% of the data: $1 \le S, N, W_i \le 10^5$, $N \times \sum_{i=1}^{S} W_i \le 10^5$, $T \le 3$.