#215524. [USACO26FEB] All Pairs Shortest Paths P

You have a bunch of triangular regions that tessellate an infinite 2D plane. The tesselation is defined as follows (see the diagram for a better understanding):

• Recall that Euler's formula states that for real . First, draw a vertex at on the complex plane for all integers .
• Then for every three vertices from the step above forming an equilateral triangle with side length 1, draw the edges forming its border. Additionally, draw a vertex at the center of the triangle and edges from the center of the triangle to each of three outer vertices.

You are given () input points, each of which lies strictly within some region (i.e., not on any vertex or edge). For any pair of the input points, define the distance between them to be the smallest number of edges crossed when drawing a path from one point to the other that doesn't pass through any vertex.

Output the sum of all pairwise distances between the input points.

The first line contains (), the number of independent tests. Each test is specified as follows: The first line contains .

The next lines each contain three integers , , and () representing a point at on the complex plane ( being a small positive number).

It is guaranteed that the sum of over all tests doesn't exceed .

For each test, output the sum of all pairwise distances on a new line.

样例输入 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

The second test is illustrated below:

• The vertex at is labeled with for each .
• Dots are drawn at the vertices mentioned above as well as the vertices that are the centers of each equilateral triangle.
• The triangular region containing is highlighted in green.
• The triangular region containing is highlighted in blue. Note that .

An example path from the first region to the second crossing three edges is drawn.

:::align{center} :::

SCORING:

• Inputs 2-5: ,
• Inputs 6-13:
• Inputs 14-21:

Problem credits: Benjamin Qi