박테리아 (큰 입력)

무한히 넓은 격자에 박테리아가 살고 있다. 박테리아 한 마리는 칸 하나를 차지한다.

1초마다 다음 변화가 모두 동시에 일어난다.

1. 북쪽 이웃 칸과 서쪽 이웃 칸에 모두 박테리아가 없는 박테리아는 죽는다.
2. 박테리아가 없는 칸의 북쪽 이웃 칸과 서쪽 이웃 칸에 모두 박테리아가 있으면 그 칸에 박테리아가 새로 태어난다.

격자를 관찰한 시점에 박테리아 수는 유한하고 한 마리 이상이며, 박테리아가 있는 칸은 직사각형 영역 한 개 또는 여러 개를 이룬다. 박테리아가 모두 죽을 때까지 몇 초가 지나는지 구하라.

아래 격자는 박테리아 6마리로 시작해 6초 뒤에 비어 있다. 1은 박테리아가 있는 칸, 0은 빈 칸이다. 그림은 1초 간격이다.

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

첫 줄에 테스트 케이스의 수 $C$가 주어진다. 각 테스트 케이스는 다음 형식으로 주어진다.

• 첫 줄에 처음에 박테리아가 있는 직사각형 영역의 수 $R$이 주어진다.
• 다음 $R$개의 줄에 공백으로 구분된 네 정수 $X_1$ $Y_1$ $X_2$ $Y_2$가 주어진다. X 좌표가 $X_1$ 이상 $X_2$ 이하이고 Y 좌표가 $Y_1$ 이상 $Y_2$ 이하인 모든 칸에 박테리아가 있다.

직사각형은 서로 겹칠 수 있다.

북쪽은 Y 좌표가 작아지는 방향이고, 서쪽은 X 좌표가 작아지는 방향이다.

제한

• $1 \le C \le 25$
• $1 \le R \le 1000$
• $1 \le X_1 \le X_2 \le 500$
• $1 \le Y_1 \le Y_2 \le 500$

각 테스트 케이스마다 Case #N: T 형식으로 한 줄을 출력한다. $N$은 1부터 시작하는 테스트 케이스 번호이고, $T$는 박테리아가 모두 죽을 때까지 걸리는 시간을 초 단위로 나타낸 값이다.