Problem
Oh no! The delicate political balance of the world has finally collapsed, and everybody has declared war on everybody else. You warned whoever would listen that this would happen, but did they pay attention? Ha! Now the only thing you can hope for is to survive as long as possible.
Fortunately (sort of), everyone's industrial centers have already been nuked, so the only method of attack available to each nation is to hurl wave after wave of conscripted soldiers at each other. This limits each nation to attacking only its immediate neighbors. The world is a R-by-C grid with R rows, numbered from 1 in the far North to R in the far South, and C columns, numbered from 1 in the far West to C in the far East. Each nation occupies one square of the grid, which means that each nation can reach at most 4 other adjacent nations.
Every nation starts with a specific strength value, known to everyone. They have no concept of advanced strategy, so at the beginning of each day, they will simply choose their strongest neighbor (breaking ties first by Northernmost nation, then by Westernmost) and attack them with an army. The army will have a power equal to the current strength S of the nation; by the end of the day, it will have depleted that neighbor's strength by S. A nation whose strength reaches 0 is destroyed. Note that all nations attack at the same time; an army's power is the same regardless of whether its nation is attacked that day.
Your nation is located at (c, r), in row r and column c. Fortunately, your nation is listening to your advice, so you don't have to follow this crazy strategy. You may choose to attack any of your neighbors on a given day (or do nothing at all). You can't attack multiple neighbors, however, or attack with an army of less than full power.
Determine the maximum number days you can survive.
Input
The first line of input gives the number of cases, T. T test cases follow. The first line of each test case contains four integers, C, R, c, and r. The next R lines each contain C integers, giving the starting strength Sci,ri of the nation in column ci and row ri. It may be 0, indicating that the nation has already been destroyed. Your nation's starting strength will not be 0.
Output
For each test case, output one line containing "Case #A: " followed by:
- "B day(s)", where B is the most days you can hope to survive.
- "forever", if you can outlast all your neighbors.
Limits
Time limit: 30 4 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100
1 ≤ c ≤ C
1 ≤ r ≤ R
Small dataset (Test set 1 - Visible; 8 Points)
1 ≤ C ≤ 5
1 ≤ R ≤ 5
0 ≤ Sci,ri ≤ 10
Large dataset (Test set 2 - Hidden; 14 Points)
1 ≤ C ≤ 50
1 ≤ R ≤ 50
0 ≤ Sci,ri ≤ 1000
Sample
2 3 3 2 2 2 3 2 1 7 1 2 1 2 4 3 2 1 1 2 2 0 10 8 5 10 10 2 9 10
Case #1: forever Case #2: 3 day(s)