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 positive integers satisfying the condition is finite.

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

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$

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

• $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.

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

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