Mondriaan

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.

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.)

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