박테리아

무한히 넓은 격자에 박테리아가 살고 있다. 한 칸에 들어가는 박테리아는 최대 한 마리다.

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

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

처음 격자에는 박테리아가 한 마리 이상 유한하게 있고, 박테리아가 있는 칸은 한 개 이상의 직사각형 영역을 이룬다.

박테리아가 모두 죽기까지 몇 초가 걸리는지 구하라.

아래 격자는 박테리아 여섯 마리로 시작해 6초 뒤에 전멸한다. 1은 박테리아가 있는 칸, 0은 빈 칸이다. 맨 왼쪽 열이 X = 1, 맨 위 행이 Y = 1이다.

t = 0      t = 1      t = 2      t = 3      t = 4      t = 5      t = 6
000010     000000     000000     000000     000000     000000     000000
011100     001110     000110     000010     000000     000000     000000
010000     011000     001100     000110     000010     000000     000000
010000     010000     011000     001100     000110     000010     000000
000000     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 100$
• $1 \le R \le 10$
• $1 \le X_1 \le X_2 \le 100$
• $1 \le Y_1 \le Y_2 \le 100$
• 처음에 박테리아가 있는 칸의 수는 1000000개 이하이다.

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