题目描述

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

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

现在有 $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"）。

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

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 完成