직사각형이 나눈 영역의 개수

x-y 평면에 직사각형 여러 개가 놓여 있다. 각 직사각형의 네 변은 x축 또는 y축과 평행하고, 모든 직사각형은 입력에서 정한 좌표 범위 안에 있다. 좌표에 다른 제약은 없다.

직사각형의 변은 평면을 여러 영역으로 나눈다. 한 영역의 경계가 직사각형 한 개의 변으로만 이루어질 수도 있고, 여러 직사각형의 변이 섞여 있을 수도 있다. 힌트의 그림 1에서는 직사각형 세 개가 서로 겹쳐서 평면이 여덟 개 영역으로 나뉜다.

직사각형은 더 복잡하게 겹칠 수도 있다. 두 직사각형이 변의 일부만 공유하거나, 꼭짓점 하나에서만 맞닿거나, 한쪽이 다른 쪽 안에 완전히 들어갈 수도 있다. 그림 2가 그런 경우를 보여 준다.

직사각형의 변이 평면을 몇 개 영역으로 나누는지 세는 프로그램을 작성하시오.

입력은 데이터 세트 여러 개로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

n
l1 t1 r1 b1
l2 t2 r2 b2
...
ln tn rn bn

데이터 세트의 첫째 줄에 평면에 놓인 직사각형의 개수 $n$이 주어진다. ($1 \le n \le 50$)

이어지는 $n$개 줄에 직사각형이 한 줄에 하나씩 주어진다. 각 줄에는 정수 네 개 $l_i$, $t_i$, $r_i$, $b_i$가 공백 하나로 구분되어 주어진다. $(l_i, t_i)$는 $i$번째 직사각형의 왼쪽 위 꼭짓점의 x-y 좌표이고, $(r_i, b_i)$는 오른쪽 아래 꼭짓점의 좌표다. ($0 \le l_i < r_i \le 10^6$, $0 \le b_i < t_i \le 10^6$)

입력의 마지막 줄에는 0 하나만 주어진다.

각 데이터 세트마다 직사각형의 변이 평면을 나눈 영역의 개수를 한 줄에 출력한다. 평면 전체를 세므로, 모든 직사각형의 바깥에 있는 무한히 넓은 영역도 영역 하나로 센다.

그림 1. 직사각형 세 개가 평면을 여덟 개 영역으로 나눈다. 예제의 첫 번째 데이터 세트에 해당한다. x축과 y축은 설명을 위해 그린 것이므로 평면을 나누지 않는다.

그림 2. 더 복잡하게 겹친 직사각형. 예제의 두 번째 데이터 세트에 해당한다.