몬드리안

시간 제한1초메모리 제한128 MB

요약

큰 직사각형을 빈틈없이 채우는 직사각형들이 주어질 때, 변으로 맞닿은 영역은 다른 색이 되도록 흰색을 포함해 칠하는 경우의 수를 센다.

문제

위대한 네덜란드 화가 피트 몬드리안(Piet Mondriaan, 1872–1944)은 최초의 현대 화가 중 한 명으로 꼽힌다. 그의 작품 상당수는 여러 개의 직사각형 영역으로 나뉘어 있다. 일부 영역은 색으로 칠해지고, 나머지는 흰색으로 남는다.

몬드리안의 채색은 보통 다음 규칙을 따른다.

그림이 영역으로 분할된 뒤에도 색을 채우는 방법은 여러 가지가 있다. 주어진 분할에 대해 서로 다른 채색 방법이 몇 가지인지 구하여라. 이 문제에서 다루는 그림에 대해 이 값은 $10^6$ 을 넘지 않는다.

꼭짓점 한 점에서만 맞닿는 두 영역은 인접한 것으로 보지 않는다.

첫째 줄에는 테스트 케이스의 수가 하나 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

첫째 줄에 그림에 있는 영역의 수 $n$ 이 주어진다 ( $1 \le n \le 100$ ).
이어지는 $n$ 개의 줄에는 각 영역의 마주 보는 두 꼭짓점의 좌표를 나타내는 네 개의 음이 아닌 정수 $x_1, y_1, x_2, y_2$ 가 주어진다 ( $0 \le x_1, x_2, y_1, y_2 \le 10^9$ ). 모든 영역은 넓이가 0이 아니며, 서로 겹치지 않고, 영역들의 합집합은 하나의 직사각형 그림을 이룬다. (따라서 위 그림은 이 문제에서 올바르지 않은 입력이다.)

각 테스트 케이스마다 그림을 색칠할 수 있는 방법의 수를 한 줄에 하나씩 출력한다.

예제 1

입력

2
2
100 110 70 105
100 105 12345 110
4
0 0 1 1
0 1 1 2
1 0 2 1
1 1 2 2

예상 출력

13
121