你有一堆平铺在无限二维平面上的三角形区域。 该平铺方式定义如下（详见示意图以获得更好的理解）：

• 回顾欧拉公式 $e^{ix}=\cos (x)+i\sin (x)$（对于实数 $x$）。首先，在复平面上对于所有整数 $x,y$，在 $x+y\exp(\pi i/3)$ 处绘制一个顶点。
• 然后，对于上述步骤中每三个构成边长为 1 的等边三角形的顶点，绘制构成其边界的边。此外，在三角形中心绘制一个顶点，并绘制从三角形中心到三个外顶点的边。

给定 $N$ ($2\le N\le 2\cdot 10^5$) 个输入点，每个点都严格位于某个区域内（即不在任何顶点或边上）。对于任意一对输入点，定义它们之间的距离为：在绘制一条不经过任何顶点的路径从一点到另一点时，所穿过的最少边数。

输出所有 $N(N-1)/2$ 对输入点之间的距离之和。

输入格式

第一行包含 $T$ ($T\ge 1$)，表示独立测试用例的数量。每个测试用例的格式如下：

第一行包含 $N$。

接下来的 $N$ 行，每行包含三个整数 $x$、$y$ 和 $z$ ($0\le x,y< 10^6, 0\le z< 12$)，表示复平面上的点 $x+y\exp(\pi i/3)+ \epsilon\cdot \exp((1+2z)\pi i/12)$（其中 $\epsilon$ 为一个很小的正数）。

保证所有测试用例的 $N$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，在一行中输出所有 $N(N-1)/2$ 对点之间的距离之和。

样例

输入 1

6
2
0 0 0
0 0 0
2
0 0 0
1 1 7
2
0 0 0
0 0 6
3
0 0 1
0 0 5
0 0 9
2
0 2 11
1 1 1
2
2 0 11
1 1 1

输出 1

0
3
6
12
2
6

说明 1

第二个测试用例说明如下：

• 对于每个 $x\in[-1,2], y\in[-1,2]$，位于 $x+y\exp(\pi i/3)$ 的顶点被标记为 $(x,y)$。
• 在上述提到的顶点以及每个等边三角形的中心顶点处绘制点。
• 包含 $(x,y,z)=(0,0,0)$ 的三角形区域以绿色高亮显示。
• 包含 $(x,y,z)=(1,1,7)$ 的三角形区域以蓝色高亮显示。注意 $15\pi/12=225^{\circ}$。
• 图中绘制了一条从第一个区域到第二个区域穿过三条边的示例路径。

子任务

• 输入 2-5：$N\le 10$, $0\le x,y< 5$
• 输入 6-13：$N\le 10$
• 输入 14-21：$T=1$