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.
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.
For each test case, output one line containing "Case #A: " followed by:
1 ≤ T ≤ 100
1 ≤ c ≤ C
1 ≤ r ≤ R
1 ≤ C ≤ 5
1 ≤ R ≤ 5
0 ≤ Sci,ri ≤ 10
1 ≤ C ≤ 50
1 ≤ R ≤ 50
0 ≤ Sci,ri ≤ 1000