Largest Rectangle in a Binary Matrix

Given a 2D binary matrix (i.e., containing only 0's and 1's), find the area of the largest rectangle composed entirely of 1's.

The typical approach is to treat each row as the base of a histogram and then use a stack-based method to find the maximum rectangular area in that histogram. In each histogram, the area is calculated by the formula \( \text{area} = \text{height} \times \text{width} \).

inputFormat

The input is given via stdin. The first line contains an integer \(T\), the number of test cases. Each test case begins with a line containing two integers \(R\) and \(C\) which denote the number of rows and columns respectively. This is followed by \(R\) lines, each containing \(C\) space-separated integers (0 or 1) representing the matrix.

outputFormat

For each test case, output a single line to stdout containing one integer: the area of the largest rectangle consisting only of 1's.

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

4
9
1
0
6