Pang 教授正在玩跳棋。游戏棋盘与上图所示相同。棋盘上有 $n$ 枚棋子。Pang 教授想知道当前棋盘上有多少种不同的走法。

一次走法由若干步组成。首先，Pang 教授需要选择一枚棋子 $a$ 进行移动。在每一步中，Pang 教授需要选择另一枚棋子 $b$ 作为支点，并将棋子 $a$ 移动到关于棋子 $b$ 对称的位置。（在一次走法中，Pang 教授在各步之间不能更换所选的棋子 $a$。如果某一步之后，棋子 $a$ 回到了该次走法开始前的位置，则该步是不允许的。）关于支点 $b$ 有以下几点要求：

• 连接 $a$ 和 $b$ 的线段需要平行于坐标轴之一。注意：六角棋盘上有三条坐标轴。其中一条是水平的，且任意两条轴之间的夹角为 $\pi/3$。
• $a$ 和 $b$ 不需要相邻。
• 连接 $a$ 和其对称位置的线段上，除了 $b$ 之外不能有其他棋子。
• 对称位置必须在六角棋盘内，且不能被其他任何棋子占据。

一次走法必须至少包含一步。在第一步之后，Pang 教授可以在任何时候停止。Pang 教授可以选择棋盘上的任意棋子作为移动棋子。输出 Pang 教授可以做出的不同走法的数量。当且仅当两次走法后所有棋子的位置集合不同时，这两次走法才被视为不同，即棋子是不可区分的。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 121$)，表示棋子的数量。

接下来的 $n$ 行，每行包含两个整数，表示一枚棋子的位置。第一个数字表示它所在的行，第二个数字表示它是该行中的第几枚。行数从上到下计数，列数从左到右计数，均从 1 开始。

保证棋子的位置各不相同。

输出格式

对于每个测试用例，输出一行一个整数，表示不同走法的数量。

样例

输入 1

5
1
1 1
2
1 1
2 1
2
9 4
9 6
10
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4

输出 1

0
1
2
6
13