题目描述

Prof. Pang is playing Chinese Checkers. The game board is the same as the figure shown above. There are $n$ checkers on the board. Prof. Pang wants to know how many different moves there are on the current board.

One move consists of several steps. At first, Prof. Pang needs to choose one checker $a$ to move. In each step, Prof. Pang needs to choose another checker $b$ as the pivot, and move the checker $a$ to the symmetrical position about the checker $b$. (In one move, Prof. Pang cannot change his choice of $a$ between steps. If after a step, the checker $a$ will return to its position before the move, this step is not allowed.) There are several conditions about the pivot $b$:

• The segment connecting $a$ and $b$ needs to be parallel to one of the coordinate axis. Note: There are three axes on the hexagonal board. One of them is horizontal and any pair of axes intersect at an angle of $\pi/3$.
• $a$ and $b$ do not need to be adjacent.
• There cannot be extra checkers other than $b$ on the segment connecting $a$ and its symmetrical position.
• The symmetrical position should be on the hexagonal board and is not occupied by any other checker.

A move must have at least one step. After the first step, Prof. Pang can stop at any time he wants. And Prof. Pang can choose any checker on the board as the moving checker. Output the number of different moves Prof. Pang can make. Two moves are different if and only if the sets of positions of all checkers are different after these two moves, i.e., the checkers are indistinguishable.

输入格式

The first line contains an integer $T~(1\leq T\leq 100)$ -- the number of test cases.

For each test case, the first line contains an integer $n~(1\leq n\leq 121)$ -- the number of checkers.

Each of the following $n$ lines contains two integers, indicating the position of a checker. The first number indicates which row it is in, and the second number indicates which one of this row it is. They are counting from top to bottom and left to right, starting from $1$.

It is guaranteed that checkers' positions are different.

输出格式

For each test case, output one integer in a line -- the number of different moves.

题目大意

棋盘上有 $n$ 个棋子，你需要求对于当前局面，下一次移动有多少种不同的走法。

一次移动由若干步组成。假设当前要移动的棋子为 $a$，在每一步中，首先需要选择另一个棋子 $b$ 作为跳台，然后将 $a$ 走到关于 $b$ 的对称位置（在一次移动中，你无法更改需要移动的棋子 $a$。并且在某一步中，棋子 $a$ 回到此次移动前所在的位置是不被允许的）。

关于跳台 $b$ 的选择有一些条件：

• $a$ 和 $b$ 之间的连线应当平行于棋盘的某条坐标轴。注：棋盘上一共有三条坐标轴，其中一条与水平线平行，并且任意两条坐标轴之间的夹角均为 $\frac{\pi}{3}$。

• $a$ 和 $b$ 不必相邻。

• 除了跳台 $b$ 以外，$a$ 和其关于 $b$ 的对称点的连线上不能有其他棋子。

• 对称点的位置应当落在棋盘上，并且没有被其他棋子占据。

一次移动需要至少走一步。在第一步以后，你可以随时停下来。你可以选择棋盘上任意一个棋子作为移动棋子。请输出有多少种不同的走法。

两种走法不同当且仅当两次移动后所有棋子的位置组成的集合不同，并且棋子之间不可区分。

输入格式

第一行一个整数 $T$，表示数据组数。

对于每组数据，第一行一个整数 $n$，表示棋子数量。

接下来 $n$ 行，每行两个整数，表示棋子位置。第一个整数表示棋子所在行，第二个整数表示棋子所在列（棋子在这一行的第几个位置上，注意每一行的起始位置和列数有可能是不一样的）。行列的编号从 $1$ 开始，分别从上到下，从左到右递增。

保证每个棋子的位置互不相同。

输出格式

输出 $T$ 行，每行一个整数，表示不同走法的数量。

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

0
1
2
6
13