题目描述

你大概听说过经典游戏“石头、剪刀、布”。奶牛们也喜欢玩一个类似的版本，叫作“蹄、纸、剪刀”。

规则与常见版本相同：

• 蹄胜剪刀
• 剪刀胜纸
• 纸胜蹄

如果双方出的手势相同，则这一局平局。

现在有 \(N\) 头奶牛想玩这个游戏，满足 \(3 \le N \le 2 \cdot 10^5\)。第 \(i\) 头奶牛并不会固定出某一个手势，而是会按照一个固定概率分布随机出招：

• 以概率 \(\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}\) 出剪刀

其中 \(0 \le h_i,p_i,s_i \le 10^9\)，并且 \(h_i+p_i+s_i>0\)。

如果奶牛 \(A\) 与奶牛 \(B\) 对局时，\(A\) 的获胜概率大于 \(B\) 的获胜概率，那么称 \(A\) “平均意义下战胜” \(B\)。

请你求出有多少个不同的三元组 \((A,B,C)\)，满足：

• \(A\) 平均意义下战胜 \(B\)
• \(B\) 平均意义下战胜 \(C\)
• \(C\) 平均意义下战胜 \(A\)

如果两个三元组只相差一个循环位移，就认为它们是同一个三元组。例如 \((A,B,C)\)、\((B,C,A)\)、\((C,A,B)\) 算同一个。

输入格式

第一行包含整数 \(T\)，表示测试组数，满足 \(1 \le T \le 5 \cdot 10^4\)。

每组测试数据格式如下：

• 第一行一个整数 \(N\)
• 接下来 \(N\) 行，每行三个非负整数 \(h_i,p_i,s_i\)

根据官方测试数据，所有测试中 \(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：无额外限制

命题信息

原题命题：Richard Qi