F :: Fields and Farmers

Time Limit: 3 Seconds    Memory Limit: 131072 KB

Being a farmer in Ardenia is a tough job. We do not mean only the dry and hostile environment where they have to pasture sheep. The government (or actually the king himself) wants his people to invade foreign lands rather than to harvest theirs, and thus tries to make the lives of poor farmers as hard as possible. All difficulties start with a seemingly simple task: purchasing a piece of land, called farming parcel.

The whole farming territory is a huge rectangular grid consisting of square fields; a farming parcel consists of some of these fields. At the beginning a farmer buys an initial set of fields; his parcel consists initially just of these fields. However, the actual farming parcel is determined with the help of string and poles, by repeating the following steps.

 

1. Stick a pole into the middle of each field from the farming parcel.
2. Surround the poles with a string, creating the smallest region enclosing all the poles.
3. The new farming parcel is the set of all fields having a non-empty intersection with this region. A field sharing just the edge or a corner with the region does not count.

Of course, the parcel may only increase by implementing the operation above, so each farmer makes sure these steps are repeated till the farming parcel does not change; we call such a parcel final. An example is depicted below. The initial farming parcel consists of four fields (figure A), after one iteration it grows (figure B), and after another one it becomes final (figure C).

 

It appears, however, that the final farming parcel would sometimes be the same even if the farmer did not buy all the initial fields but just a subset of them. A subset of this property is called valid. The farmer wants to know in how many ways he may choose a valid subset of initial fields.

Input

The input contains several test cases. The first line of the input contains a positive integer Z <=50, denoting the number of test cases. Then Z test cases follow, each conforming to the format described below.

The first line of the input instance contains a positive integer n <=10⁶ , being the number of initial fields of the parcel. Each of the following n lines contain two integers x_i, y_i є [- 10⁹, 10⁹], being the coordinates of these fields. All initial fields are different.

Output

For each test case, your program has to write an output conforming to the format described below.

Let k be the number of valid subsets of the initial fields. You should output a line containing the number k mod(10⁹ + 7).

Sample Input

2 
4 
0 0 
0 1 
0 2 
0 3 
5 
0 0 
-1 0 
1 0 
0 -1 
0 1

Sample Output

4
2

Submit

Source: Central European Regional Contest 2010