题目描述

你可能听说过游戏“石头、布、剪刀”。奶牛们喜欢玩一个类似的游戏，他们称之为“蹄子、布、剪刀”。

“蹄子、布、剪刀”的规则很简单。两头奶牛相互对战。它们都数到三，然后同时做出一个手势，代表蹄子、布或剪刀。蹄子赢剪刀（因为蹄子可以砸碎剪刀），剪刀赢布（因为剪刀可以剪布），布赢蹄子（因为蹄子可能被布划伤）。例如，如果第一头奶牛做出“蹄子”手势，第二头奶牛做出“布”手势，那么第二头奶牛获胜。当然，如果两头奶牛做出相同的手势，也可能平局。

现在有 $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,C)$，使得 $A$ 平均赢 $B$，$B$ 平均赢 $C$，且 $C$ 平均赢 $A$？如果两个三元组通过循环移位相等，我们视为同一个三元组。

输入格式

第一行包含 $T$（$1\le T\le 5\cdot 10^4$），表示独立测试的数量。每个测试按以下格式指定：

第一行包含 $N$。

接下来的 $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$ 之和不超过 $3\cdot 10^5$。

输出格式

输出三元组的数量。

注意：本题涉及的大整数可能需要使用 64 位整数数据类型（例如，C/C++ 中的 "long long"）。

输入输出样例 #1

输入 #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

说明/提示

对于第一个测试用例，有两个三元组：$(1, 3, 4)$ 和 $(2, 3, 4)$。

• 输入 $2$-$3$：$N\le 10$
• 输入 $4$-$9$：$N \le 7500$，所有测试的 $N$ 之和不超过 $10^4$
• 输入 $10$-$21$：无额外约束。

翻译由 DeepSeek V3 完成