A number of bacteria lie on an infinite grid of cells, each bacterium in its own cell.
Each second, the following transformations occur (all simultaneously):
Upon examining the grid, you note that there are a positive, finite number of bacteria in one or more rectangular regions of cells.
Determine how many seconds will pass before all the bacteria die.
Here is an example of a grid that starts with 6 cells containing bacteria, and takes 6 seconds for all the bacteria to die. '1's represent cells with bacteria, and '0's represent cells without bacteria.
000010 011100 010000 010000 000000 000000 001110 011000 010000 000000 000000 000110 001100 011000 000000 000000 000010 000110 001100 000000 000000 000000 000010 000110 000000 000000 000000 000000 000010 000000 000000 000000 000000 000000 000000
The input consists of:
North is in the direction of decreasing Y coordinate.
West is in the direction of decreasing X coordinate.
For each test case, output one line containing "Case #N: T", where N is the case number (starting from 1), and T is the number of seconds until the bacteria all die.
1 ≤ C ≤ 100.
1 ≤ R ≤ 10
1 ≤ X_{1} ≤ X_{2} ≤ 100
1 ≤ Y_{1} ≤ Y_{2} ≤ 100
1 ≤ R ≤ 1000
1 ≤ X_{1} ≤ X_{2} ≤ 1000000
1 ≤ Y_{1} ≤ Y_{2} ≤ 1000000
The number of cells initially containing bacteria will be at most 1000000.
Input 
Output 
1 
Case #1: 6
