문제

지현이는 무한한 2차원 평면이 정삼각형 모양의 영역들로 타일링되어 있는 구조를 연구하고 있다. 타일링은 다음과 같이 정의된다.

먼저, 모든 정수 $x, y$에 대해 복소평면 위의 $x + y ext{exp}(\pi i/3)$ 지점에 정점을 그린다. (오일러 공식에 의해 실수 $x$에 대해 $e^{ix} = \cos(x) + i\sin(x)$이다.)

그 후, 위 단계에서 생성된 정점들 중 한 변의 길이가 $1$인 정삼각형을 이루는 세 정점 사이를 잇는 변을 그린다. 추가로, 각 정삼각형의 무게중심에 정점을 하나씩 더 그리고, 그 무게중심에서 해당 정삼각형의 세 꼭짓점으로 이어지는 변을 그린다.

지현이에게 $N$ ($2 \le N \le 2 \cdot 10^5$)개의 점이 주어지며, 각 점은 어떤 영역의 내부에 위치한다. 즉, 점은 어떤 정점이나 변 위에도 놓이지 않는다. 임의의 두 점 사이의 거리는 한 점으로부터 다른 점까지 정점을 지나지 않고 이동할 때 가로지르는 변의 최소 개수로 정의한다.

주어진 $N$개의 점들 사이의 모든 $N(N-1)/2$개 쌍에 대한 거리의 총합을 구하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$ ($T \ge 1$)가 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

첫째 줄에 점의 개수 $N$이 주어진다. ($2 \le N \le 2 \cdot 10^5$)

이어서 $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$을 초과하지 않는다.

출력

각 테스트 케이스마다 모든 점 쌍 사이의 거리의 총합을 한 줄에 하나씩 출력한다.

예제 입력 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

제한

• 테스트 케이스 2~5: $N \le 10$, $0 \le x, y < 5$
• 테스트 케이스 6~13: $N \le 10$
• 테스트 케이스 14~21: $T = 1$