다가오는 종말

이런! 세계의 미묘한 정치적 균형이 마침내 무너졌고, 모두가 서로에게 전쟁을 선포했다. 당신은 귀를 기울이는 사람이라면 누구에게든 이런 일이 일어날 것이라고 경고했지만, 그들이 주의를 기울였던가? 흥! 이제 당신이 바랄 수 있는 유일한 것은 가능한 한 오래 살아남는 것뿐이다.

다행히도(어떤 의미에서는), 모두의 산업 중심지는 이미 핵 공격으로 파괴되었으므로 각 국가가 사용할 수 있는 유일한 공격 방법은 징집한 병사들을 끊임없이 서로에게 밀어 넣는 것이다. 이 때문에 각 국가는 바로 이웃한 국가만 공격할 수 있다. 세계는 R개의 행으로 이루어진 $R \times C$ 격자이며, 행에는 최북단의 1부터 최남단의 R까지 번호가 매겨져 있고, C개의 열에는 최서단의 1부터 최동단의 C까지 번호가 매겨져 있다. 각 국가는 격자의 한 칸을 차지하며, 이는 각 국가가 인접한 다른 국가를 최대 4개까지 공격할 수 있다는 뜻이다.

모든 국가는 모두에게 알려진 특정한 세력 값으로 시작한다. 이들에게는 고급 전략이라는 개념이 없으므로, 매일 시작할 때 단순히 가장 강한 이웃을 선택하고(동률이면 먼저 가장 북쪽에 있는 국가를, 그다음 가장 서쪽에 있는 국가를 선택한다) 군대로 공격한다. 군대의 위력은 해당 국가의 현재 세력 S와 같으며, 하루가 끝날 때까지 그 이웃 국가의 세력을 S만큼 감소시킨다. 세력이 0에 도달한 국가는 파괴된다. 모든 국가는 동시에 공격한다는 점에 유의하라. 군대의 위력은 그날 해당 국가가 공격받는지 여부와 관계없이 동일하다.

당신의 국가는 r행 c열의 (c, r)에 있다. 다행히 당신의 국가는 당신의 조언을 따르므로, 이 터무니없는 전략을 따를 필요가 없다. 주어진 날에 이웃 중 어느 국가든 선택하여 공격할 수 있다(또는 아무것도 하지 않을 수도 있다). 하지만 여러 이웃을 공격하거나 최대 위력보다 약한 군대로 공격할 수는 없다.

살아남을 수 있는 최대 일수를 구한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100 1 ≤ c ≤ C 1 ≤ r ≤ R

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ C ≤ 5 1 ≤ R ≤ 5 0 ≤ $S_{ci,ri}$ ≤ 10

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ C ≤ 50 1 ≤ R ≤ 50 0 ≤ $S_{ci,ri}$ ≤ 1000

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 네 정수 C, R, c, r이 주어진다. 다음 R개의 줄에는 각각 C개의 정수가 주어지며, 이는 ci열 ri행에 있는 국가의 초기 세력 $S_{ci,ri}$을 나타낸다. 이 값은 해당 국가가 이미 파괴되었음을 나타내는 0일 수도 있다. 당신 국가의 초기 세력은 0이 아니다.

각 테스트 케이스마다 "Case #A: " 뒤에 다음 중 하나를 붙인 한 줄을 출력한다.

• "B day(s)". 여기서 B는 당신이 살아남기를 기대할 수 있는 최대 일수이다.

• 모든 이웃보다 오래 살아남을 수 있다면 "forever".