Largest Rectangle in a Binary Matrix

You are given one or more binary matrices. For each matrix, your task is to compute the area of the largest rectangle that consists solely of 1's. In each matrix, the rectangle's area is defined as \(\text{area} = \text{width} \times \text{height}\). You can solve this problem efficiently by transforming each row into a histogram of consecutive ones and then applying a stack-based algorithm to determine the largest rectangle area in that histogram.

Problem Overview:

• You are given an integer \(T\) denoting the number of test cases.
• For each test case, the first line contains two integers \(h\) and \(w\) representing the number of rows and columns of the matrix, respectively.
• The next \(h\) lines contain \(w\) space-separated binary digits (either 0 or 1) representing the matrix.
• Your task is to output the area of the largest rectangle that consists entirely of 1's for each test case.

Make sure that your solution reads input from stdin and writes the output to stdout.

inputFormat

The input is given via stdin and has the following format:

T
h1 w1
row1
row2
... (h1 rows)
h2 w2
row1
row2
... (h2 rows)
...

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers \(h\) and \(w\).
• Then \(h\) lines follow, each containing \(w\) space-separated binary digits.

outputFormat

For each test case, print a single integer to stdout on a new line, which is the area of the largest rectangle composed entirely of 1's in the corresponding matrix.

## sample

1
2 2
1 1
1 1

4