문제

'가위바위보' 게임은 모두가 잘 알고 있는 게임이다. 은영이와 친구들은 이와 유사하지만 이름이 조금 다른 '발굽, 보, 가위' 게임을 즐긴다.

'발굽, 보, 가위'의 규칙은 간단하다. 두 사람이 서로 대결하며, 동시에 발굽, 보, 가위 중 하나를 낸다. 발굽은 가위를 이기고(발굽으로 가위를 부술 수 있다), 가위는 보를 이기며(가위로 종이를 자를 수 있다), 보는 발굽을 이긴다(발굽이 종이에 베일 수 있다). 만약 두 사람이 같은 것을 낸다면 비기게 된다.

현재 $N$ ($3 \le N \le 2 \cdot 10^5$)명의 친구가 이 게임을 하려 한다. 각 친구는 자신만의 고정된 확률 분포에 따라 패를 내는 전략을 가지고 있다. 구체적으로, $i$번째 친구의 전략은 발굽, 보, 가위를 각각 다음과 같은 확률로 내는 것이다.

$\left(\frac{h_i}{h_i+p_i+s_i}, \frac{p_i}{h_i+p_i+s_i}, \frac{s_i}{h_i+p_i+s_i} \right)$

평균적으로 $A$가 $B$를 이기고, $B$가 $C$를 이기며, $C$가 $A$를 이기는 서로 다른 세 친구의 쌍 $(A, B, C)$는 총 몇 개인가? 이때 두 삼쌍이 순환 이동(cyclic shift)을 통해 같아진다면 동일한 삼쌍으로 간주한다. (즉, $(A, B, C)$, $(B, C, A)$, $(C, A, B)$는 모두 같다.)

평균적으로 $A$가 $B$를 이긴다는 것은 $A$와 $B$가 게임을 할 때 $A$가 이길 확률이 $B$가 이길 확률보다 높음을 의미한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 5 \cdot 10^4$)가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

테스트 케이스의 첫째 줄에는 친구의 수 $N$이 주어진다. ($3 \le N \le 2 \cdot 10^5$)

이어서 $N$개의 줄에 각 친구의 전략을 나타내는 세 개의 음이 아닌 정수 $h_i, p_i, s_i$가 주어진다. ($0 \le h_i, p_i, s_i \le 10^9, h_i+p_i+s_i > 0$)

모든 테스트 케이스에 대한 $N$의 합은 $2 \cdot 10^5$을 초과하지 않는다.

출력

조건을 만족하는 삼쌍의 개수를 출력한다.

참고: 이 문제에서 다루는 정수의 크기가 매우 클 수 있으므로, C/C++의 long long과 같은 64비트 정수 자료형을 사용하는 것이 권장된다.

예제 입력 1

2
4
1 0 0
1 0 0
0 1 0
0 0 1
10
20410069 21445597 257862632
114108992 287498302 113278897
607994331 143503714 631122722
337497016 270153603 320256324
633717786 631078144 493265815
202783212 612643590 560838949
713379081 42803063 58996167
293262767 470686180 220651551
656404313 408797935 345461691
959196297 827681918 591519393

예제 출력 1

2
32

점수

• Inputs 2-3: $N \le 10$
• Inputs 4-9: $N \le 7\,500$, 모든 테스트 케이스의 $N$의 합이 $10^4$ 이하
• Inputs 10-21: 추가 제약 조건 없음