边长为 $$$A$$$ 和 $$$B$$$ 的矩形被切成多个矩形,切口平行于其边。例如,如果进行 $$$p$$$ 水平切割和 $$$q$$$ 垂直切割,则切割后会留下 $$$(p + 1) \cdot (q + 1)$$$ 矩形。切割后,矩形有$$$n$$$ 不同类型。如果一个矩形的至少一条边不等于另一个矩形的对应边,则两个矩形不同。请注意,矩形不能旋转,这意味着如果 $$$a \neq b$$$ ,则矩形 $$$a \times b$$$ 和 $$$b \times a$$$ 被视为不同。
对于每种类型的矩形,给出了矩形边的长度以及切割初始矩形后留下的该类型矩形的数量。
计算$$$(A; B)$$$对的数量,例如可以通过切割边长为$$$A$$$和$$$B$$$的矩形来创建给定的矩形。请注意,当 $$$A \neq B$$$ 时,$$$(A; B)$$$ 和 $$$(B; A)$$$ 被视为不同。
输入
第一行由一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$) 组成 - 切割初始矩形后剩下的不同类型矩形的数量。
接下来的 $$$n$$$ 行每行包含三个整数 $$$w_{i}, h_{i}, c_{i}$$$ $$$(1 \leq w_{i}, h_{i}, c_{i} \leq 10^{12})$$$ ——该类型矩形的边长和该类型矩形的数量。
保证不同类型的矩形是不同的。
输出
输出一个整数——问题的答案。
示例
输入 #1
1 1 1 9
输出 #1
3
输入 #2
2 2 3 20 2 4 40
输出 #2
6
输入 #3
2 1 2 5 2 3 5
输出 #3
0
注意
在第一个示例中,存在三个合适的对:$$$(1; 9)$$$、$$$(3; 3)$$$ 和 $$$(9; 1)$$$。
在第二个示例案例中,有 6 个合适的对:$$$(2; 220)$$$、$$$(4; 110)$$$、$$$(8; 55)$$$、$$$(10; 44)$$$、$$$(20; 22)$$$ 和 $$$(40; 11)$$$。
这里是 $$$(20; 22)$$$ 的切割样本。
第三个样本没有合适的对。