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 (≤ 2), 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.
Sample
| Sample Input | Sample Output |
|---|---|
2 5 7 0110110 0000010 1000001 0100001 1100010 3 3 001 100 101 | Case 1: 12 Case 2: 3 |
Notes
Dataset is huge, use faster I/O methods.