종말이 온다 (Large)

세계의 정치 균형이 끝내 무너져 모든 나라가 서로에게 전쟁을 선포했다. 산업 시설은 이미 전부 파괴되었으므로 각 나라에 남은 공격 수단은 징집한 병사를 인접국으로 몰아 보내는 것뿐이다. 그래서 어느 나라도 바로 맞닿은 나라만 공격할 수 있다.

세계는 $R$개의 행과 $C$개의 열로 이루어진 격자다. 행 번호는 가장 북쪽이 1, 가장 남쪽이 $R$이고, 열 번호는 가장 서쪽이 1, 가장 동쪽이 $C$다. 각 나라는 격자의 한 칸을 차지하므로 맞닿은 나라는 많아도 4개다.

모든 나라의 국력은 서로에게 공개되어 있다. 우리 나라를 뺀 나라는 전략이랄 것이 없어서, 매일 아침 살아 있는 인접국 중 국력이 가장 큰 나라를 목표로 정한다. 국력이 같으면 더 북쪽에 있는 나라를 고르고, 그래도 같으면 더 서쪽에 있는 나라를 고른다. 그리고 그날 아침 자기 국력 $S$와 같은 위력의 군대를 보내, 하루가 끝날 때 목표의 국력을 $S$만큼 깎는다. 국력이 0이 된 나라는 멸망한다. 멸망한 나라는 공격하지도 공격받지도 않고, 가장 강한 인접국을 고를 때 후보에서도 빠진다. 살아 있는 인접국이 하나도 없는 나라는 그날 아무 일도 하지 않는다.

모든 공격은 같은 시각에 일어난다. 군대의 위력은 그날 아침의 국력으로 정해지며, 그날 자기 나라가 공격을 받는지와는 상관이 없다.

우리 나라는 $c$열 $r$행에 있고, 다행히 우리 조언을 듣기 때문에 이 미친 전략을 따르지 않는다. 우리는 하루에 살아 있는 인접국 하나를 골라 공격할 수도 있고, 아무것도 하지 않을 수도 있다. 다만 한 날에 두 나라를 공격할 수는 없고, 그날 아침 국력보다 약한 군대를 보낼 수도 없다.

날은 1일, 2일, 3일 순서로 센다. $d$일의 공격을 모두 반영한 뒤에도 우리 국력이 0보다 크면 우리는 $d$일을 버틴 것이다. 1일부터 $D$일까지 전부 버틸 수 있는 가장 큰 $D$를 구하라. 인접국을 모두 버텨내고 끝없이 살아남을 수 있으면 그 사실을 답한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 네 정수 $C$, $R$, $c$, $r$이 주어진다. 다음 $R$개의 줄에는 각각 $C$개의 정수가 주어지고, $c_i$열 $r_i$행에 있는 나라의 시작 국력 $S_{c_i, r_i}$를 나타낸다. 이 값이 0이면 그 나라는 이미 멸망한 상태다. 우리 나라의 시작 국력은 0이 아니다.

제한

• $1 \le T \le 100$
• $1 \le c \le C \le 50$
• $1 \le r \le R \le 50$
• $0 \le S_{c_i, r_i} \le 1000$

각 테스트 케이스마다 Case #A: 뒤에 아래 내용을 붙여 한 줄로 출력한다. $A$는 1부터 시작하는 테스트 케이스 번호다.

• 버틸 수 있는 날이 최대 $B$일이면 B day(s)를 출력한다. $B$는 0일 수도 있다.
• 끝없이 살아남을 수 있으면 forever를 출력한다.