Ax + By < C

题目描述

给你三个长度为 $N$ 的正整数序列：$A=(A_1,A_2,\ldots,A_N)$、$B=(B_1,B_2,\ldots,B_N)$ 和 $C=(C_1,C_2,\ldots,C_N)$。

求满足以下条件的正整数对 $(x, y)$ 的个数：

对所有 $1 \leq i \leq N$，都有 $A_i \times x + B_i \times y \lt C_i$。

可以证明，满足条件的正整数对的个数是有限的。

给你 $T$ 个测试用例，每个测试用例都需要求解。

输入格式

输入按以下格式从标准输入给出。这里，$\mathrm{case}_i$ 表示第 $i$ 个测试用例。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例按以下格式给出：

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$

输出格式

输出 $T$ 行。第 $i$ 行 $(1 \leq i \leq T)$ 应包含第 $i$ 个测试用例的答案。

样例

2
2
1 1 4
1 2 5
1
1 1 2

2
0

第一个测试用例中，有两组合法的整数对：$(x, y) = (1, 1), (2,1)$。因此第一行应输出 $2$。

第二个测试用例中，没有合法的整数对。因此第二行应输出 $0$。

3
7
138 16011 918976
5478 7748 499926
5234 17727 748589
1157 10511 643136
31200 3005 721285
28839 14469 798851
1933 5378 864127
9
17775 1665 386430
37001 863 922418
9756 4182 746671
12379 9106 807578
3984 4049 640539
25333 9869 780810
20372 7000 688738
16107 11974 827227
10779 10531 770510
5
4916 14132 460944
11856 45422 610561
56014 18216 825793
10363 6220 945356
37418 33866 851593

660
995
140

数据范围

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i, C_i \leq 10^9$
• 所有测试用例的 $N$ 之和至多为 $2 \times 10^5$
• 输入中的所有数值均为整数