Crossfire Friends - Repovive Premier Round 5 | Repovive

13B. Crossfire Friends

1000 pts2s256 MB

There are $2n$ musketeers standing on a coordinate grid.

For each $i$ with $1 \le i \le n$ , one musketeer stands at $(0, i)$ and shoots a bullet parallel to the positive direction of the $x$ -axis.

For each $i$ with $1 \le i \le n$ , one musketeer stands at $(i, 0)$ and shoots a bullet parallel to the positive direction of the $y$ -axis.

All bullets are shot at the same time. The speed of the bullet shot from $(0, i)$ is $h_i$ units per second, and the speed of the bullet shot from $(i, 0)$ is $v_i$ units per second.

Bullets pass through each other and continue moving. If at some real time $t$ with $0 \le t \le n$ two bullets are at the same point, the two musketeers who shot them become friends.

For each test case, find the number of pairs of musketeers that become friends.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le h_i, v_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ h_1 \quad h_2 \quad \cdots \quad h_n \\ v_1 \quad v_2 \quad \cdots \quad v_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \operatorname{ans} \end{array} \right\} \times t

Samples

Input

Case 1

1
1
1

Case 2

2
1 1
1 1

Case 3

3
3 1 2
1 3 2

Case 4

4
4 2 4 1
4 1 6 1

Case 5

5
5 3 2 10 1
1 3 2 10 5

Explanation

Case 1

The only two bullets meet at point (1, 1) after 1 second.

Case 2

There are two friendly pairs. The bullets from (0, 1) and (1, 0) meet at (1, 1), and the bullets from (0, 2) and (2, 0) meet at (2, 2).

Case 3

The bullet from (0, 3) meets the bullets from (2, 0) and (3, 0). No other pair meets during the first 3 seconds.

Case 4

Six pairs meet. The bullets from (0, 1), (0, 2), and (0, 4) each meet the bullets from (1, 0) and (4, 0).

Case 5

Five pairs meet. Four of them come from the two bullets starting at (0, 2) and (0, 3) meeting the two bullets starting at (2, 0) and (3, 0). The bullet from (0, 4) also meets the bullet from (4, 0).

Output

Case 1

Case 2

Case 3

Case 4

Case 5

There are $2n$ musketeers standing on a coordinate grid.

For each $i$ with $1 \le i \le n$ , one musketeer stands at $(0, i)$ and shoots a bullet parallel to the positive direction of the $x$ -axis.

For each $i$ with $1 \le i \le n$ , one musketeer stands at $(i, 0)$ and shoots a bullet parallel to the positive direction of the $y$ -axis.

All bullets are shot at the same time. The speed of the bullet shot from $(0, i)$ is $h_i$ units per second, and the speed of the bullet shot from $(i, 0)$ is $v_i$ units per second.

Bullets pass through each other and continue moving. If at some real time $t$ with $0 \le t \le n$ two bullets are at the same point, the two musketeers who shot them become friends.

For each test case, find the number of pairs of musketeers that become friends.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le h_i, v_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ h_1 \quad h_2 \quad \cdots \quad h_n \\ v_1 \quad v_2 \quad \cdots \quad v_n \end{array} \right\} \times t

\left. \begin{array}{l} \operatorname{ans} \end{array} \right\} \times t

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

13B. Crossfire Friends

Constraints

Input

Output

Samples

13B. Crossfire Friends

Constraints

Input

Output

Samples