Largest Filled Rectangle in a Binary Grid

Given a binary grid with ( m ) rows and ( n ) columns, where each cell is either 0 (white) or 1 (black), find the area of the largest rectangle that consists solely of 1s. The rectangle must be contiguous and its sides parallel to the grid axes.

For example, for the grid below:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
The largest rectangle of 1s has an area of 6.

inputFormat

The input begins with an integer ( t ) indicating the number of test cases. For each test case, the first line contains two space-separated integers ( m ) and ( n ) (the number of rows and columns, respectively). This is followed by ( m ) lines, each containing ( n ) space-separated integers (either 0 or 1) representing the grid.

outputFormat

For each test case, output a single line containing one integer: the area of the largest rectangle composed entirely of 1s.## sample

1
4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

6