C :: Coordinate System

Time Limit: 15 Seconds    Memory Limit: 65536 KB

Inefficient Coordinates Program, Cartesian section (ICPC) has created a problem in order to show how efficient this coordinates system is: A 2D vector in Cartesian system is a pair of (a,b) where a and b are the displacements in x and y axes respectively. Adding vectors in this system is easy, you just need to sum up the values in each direction. For example, (a,b) + (c,d) is equal to (a + c,b + d). The result of the sum of vectors is also a vector. In some cases the sum of two vectors has a larger length than any of them and sometimes it gets smaller. Even there are cases that the sum of multiple vectors has length zero! Another interesting fact about adding vectors is that the order doesn’t matter! You can sum them up in any order you want and the result would remain the same. Given a set of N 2D vectors in Cartesian system, find the number of subsets so that the sum of the vectors in that subset has length zero.

Input

The input contains several test cases.

In the first line of input comes T (0 < T ≤ 20), the number of test cases.

The first line of each test case contains N ≤ 40, the number of vectors. The next N lines describe each vector. Each line contains two integers x and y where |x|,|y|≤ 10 and no vector has a zero length.

Output

For each test case, output on a single line containing the number of subsets with sum of zero length.

Sample Input

1
5
1 2
1 1
-1 -2
-2 -3
-1 -1

Sample Output

4

Submit

Source: 13th Iran Nationwide Internet Contest - UT