Mondriaan

Time limit1sMemory limit128 MB

Summary

Given non-overlapping rectangles that tile a big rectangle, count the 3-colorings of the adjacency graph where orthogonally touching regions differ and white is a fourth free option.

Level: Medium7 of 10
Topics: Geometry, Graph, DFS, Dynamic programming
Solved: No attempts yet

Problem

The great Dutch painter Piet Mondriaan (1872–1944) is regarded as one of the first modern painters. Many of his compositions are divided into several rectangular regions. Some regions are filled with a color, while the others are left white.

Mondriaan's colorings usually obey the following rules:

Every colored region is red, yellow, or blue.
Two regions that are adjacent (horizontally or vertically) must not have the same color. White is not considered a color, so two adjacent regions may both be white.

Once a painting has been divided into regions, there are still many ways to fill them with colors. For a given division, determine how many different colorings are possible. For the paintings considered here, this number does not exceed $10^6$ .

Two regions that touch only at a corner point are not considered adjacent.

Input

The first line contains a single integer: the number of test cases. Each test case has the following format:

One line with a positive integer $n$ ( $1 \le n \le 100$ ): the number of regions in the painting.
$n$ lines, each containing four non-negative integers $x_1, y_1, x_2, y_2$ ( $0 \le x_1, x_2, y_1, y_2 \le 10^9$ ): the coordinates of two opposite corners of a region. Every region has non-zero area, regions do not overlap, and the union of the regions forms a single rectangular painting. (Therefore, the illustration above would be an invalid input for this problem.)

Output

For each test case, output on a single line the number of ways the painting can be colored.

Examples3

Example 1

Input

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

Expected output

13
121

Example 2
Input
```
1
1
0 0 5 5
```
Expected output
```
4
```
Example 3
Input
```
1
2
0 0 1 1
1 0 2 1
```
Expected output
```
13
```