몬드리안

위대한 네덜란드 화가 피트 몬드리안(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이 아니며, 서로 겹치지 않고, 영역들의 합집합은 하나의 직사각형 그림을 이룬다. (따라서 위 그림은 이 문제에서 올바르지 않은 입력이다.)

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