Server Time: Wed Sep 26, 2018 3:08 pm
 Welcome ( logout )
1424 - New Land
 PDF (English) Statistics Forum
 Time Limit: 5 second(s) Memory Limit: 64 MB

Once upon a time there lived an old wise king. He had only one son. The prince had the idea that he (the prince) was about to be the future king; that's why he became too lazy day by day. This made the wise king a bit worried because his lazy son couldn't be the correct man for the throne. He couldn't sleep; his kingdom was in need of a perfect king, not the lazy king.

One day, while doing his regular works, he found an excellent idea. Next day he called his son. He said that he wanted the prince to have his own kingdom. The prince became very excited. The king continued that the prince can have a land from the king's kingdom, but he should start walking after sunrise and cover a rectangular area before sunset. Then the land would be given to the prince. The lazy prince thought, "It would be an easy task!" That's why he wanted to find the maximum rectangular area in king's land. But there were some rocks in the kingdom, and the prince didn't want any rocks in his new land. He would rather take nothing, but no rocks.

The kingdom can be thought as an m x n grid, where m is the number of rows and n is the number of columns. Each cell in the grid is a small rectangular land whose area is one. If a land contains rock it will be denoted by a 1, otherwise it will be denoted by a 0. The prince can walk in the sides of the cells and he can either take a cell (land) or ignore it, but he can't take a part of a cell. Now your task is to find the maximum rectangular area the prince could cover.

# Input

Input starts with an integer T (≤ 4), denoting the number of test cases.

Each case starts with a line containing two integers: m and n (1 ≤ m, n ≤ 2000). Each of the next m lines contains n characters (either 0 or 1) denoting the kingdom.

# Output

For each case, print the case number and the maximum rectangular area the prince could take.

2

5 7

0110110

0000010

1000001

0100001

1100010

3 3

001

100

101

Case 1: 12

Case 2: 3

# Note

Dataset is huge, use faster I/O methods.

Problem Setter: Jane Alam Jan
Special Thanks: Md. Towhidul Islam Talukder
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan