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