Description

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

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

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

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

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

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

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

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

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

Input Format

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

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

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

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

Output Format

输出 $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