박테리아

무한한 셀 격자 위에 여러 박테리아가 있으며, 각 박테리아는 서로 다른 셀에 있다.

매초 다음 변화가 모두 동시에 일어난다:

• 어떤 박테리아의 북쪽에도 이웃 박테리아가 없고 서쪽에도 이웃 박테리아가 없으면, 그 박테리아는 죽는다.

• 어떤 셀에 박테리아가 없지만 북쪽과 서쪽의 이웃 셀에 박테리아가 있으면, 그 셀에서 새로운 박테리아가 태어난다.

격자를 살펴보니, 하나 이상의 직사각형 셀 영역에 양의 유한한 수의 박테리아가 있음을 알게 되었다.

모든 박테리아가 죽을 때까지 몇 초가 걸리는지 구한다.

다음은 처음에 6개의 셀에 박테리아가 있으며, 모든 박테리아가 죽는 데 6초가 걸리는 격자의 예제이다. '1'는 박테리아가 있는 셀을 나타내고, '0'는 박테리아가 없는 셀을 나타낸다.

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

제한

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

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

1 ≤ R ≤ 10 1 ≤ $X_{1}$ ≤ $X_{2}$ ≤ 100 1 ≤ $Y_{1}$ ≤ $Y_{2}$ ≤ 100

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

1 ≤ R ≤ 1000 1 ≤ $X_{1}$ ≤ $X_{2}$ ≤ 1000000 1 ≤ $Y_{1}$ ≤ $Y_{2}$ ≤ 1000000

처음에 박테리아가 있는 셀의 수는 최대 1000000개이다.

입력은 다음과 같이 구성된다:

• 테스트 케이스의 수 C가 포함된 한 줄. 이어서 각 테스트 케이스마다 다음이 주어진다:

• 처음에 박테리아가 있는 셀들의 직사각형 수 R이 포함된 한 줄.

• 공백으로 구분된 네 정수 $X_{1}$ $Y_{1}$ $X_{2}$ $Y_{2}$가 포함된 R개의 줄. 이는 X 좌표가 $X_{1}$ 이상 $X_{2}$ 이하이고 Y 좌표가 $Y_{1}$ 이상 $Y_{2}$ 이하인 모든 셀에 박테리아가 있음을 나타낸다. 직사각형들은 서로 겹칠 수 있다.

북쪽은 Y 좌표가 감소하는 방향이다. 서쪽은 X 좌표가 감소하는 방향이다.

각 테스트 케이스마다 "Case #N: T"을 포함하는 한 줄을 출력한다. 여기서 N은 테스트 케이스 번호이며(1부터 시작), T는 모든 박테리아가 죽을 때까지 걸리는 초의 수이다.