103726: [Atcoder]ABC372 G - Ax + By < C

Problem Statement

You are given three length-$N$ sequences of positive integers: $A=(A_1,A_2,\ldots,A_N)$, $B=(B_1,B_2,\ldots,B_N)$, and $C=(C_1,C_2,\ldots,C_N)$.

Find the number of pairs of positive integers $(x, y)$ that satisfy the following condition:

• $A_i \times x + B_i \times y < C_i$ for all $1 \leq i \leq N$.

It can be proved that the number of such pairs of non-negative integers satisfying the condition is finite.

You are given $T$ test cases, each of which should be solved.

Constraints

• $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$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ refers to the $i$-th test case.

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

Each test case is given in the following format:

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

Output

Print $T$ lines. The $i$-th line $(1 \leq i \leq T)$ should contain the answer for $\mathrm{case}_i$.

Sample Input 1

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

Sample Output 1

2
0

In the first query, there are two valid pairs of integers: $(x, y) = (1, 1), (1, 2)$. Thus, the first line should contain $2$.

In the second query, there are no valid pairs of integers. Thus, the second line should contain $0$.

Sample Input 2

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

Sample Output 2

660
995
140

问题陈述

给定三个长度为$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 < C_i$。

可以证明，满足该条件的非负整数对的数量是有限的。

你有$T$个测试用例需要解决。

约束条件

• $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$。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出。这里，$\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$）应包含$\mathrm{case}_i$的答案。

示例输入 1

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

示例输出 1

2
0

在第一个查询中，有两个有效的整数对：$(x, y) = (1, 1), (1, 2)$。因此，第一行应包含$2$。

在第二个查询中，没有有效的整数对。因此，第二行应包含$0$。

示例输入 2

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

示例输出 2

660
995
140