Ball Game

N

N balls are placed at distinct coordinates on the

X

Xaxis. The initial coordinate of the

i

t

h

i

th

ball is given as

A

i

$($

A

i

$>$

$0$

$)$

A

i

$($A

i

$>0).$

A hole is present at the origin. The

i

t

h

i

th

ball moves towards the hole with a speed of

B

i

B

i

units per second.

If multiple balls collide before reaching the hole, they merge into one ball, taking the maximum speed of the initial balls.

Determine the number of balls that will reach the hole considering all possible collisions along the way.

Note that collisions do not occur at the hole. Thus, if multiple balls reach the hole at the same time, all are counted separately.

Input Format

The first line of input will contain a single integer

T

T$,$ denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line of each test case contains a single integer

N

N the number of balls.

The second line contains

N

N distinct positive integers

A

$1$

$,$

A

$2$

$,$

$,$

A

N

A

$1$

$,$A

$2$

$,,$A

N

the initial coordinates of balls.

The third line contains

N

N integers

B

$1$

$,$

B

$2$

$,$

$,$

B

N

B

$1$

$,$B

$2$

$,,$B

N

the speed with which the

i

t

h

i

th

ball is moving towards the hole.

Output Format

For each test case, print a single integer denoting the number of balls that reach the hole.

Constraints

$1$

T

$1$

$0$

$4$

$1$T$10$

$4$

$1$

N

$2$

$1$

$0$

$5$

$1$N$210$

$5$

$1$

A

i

$1$

$0$

$9$

$,$

A

i

$1$A

i

$10$

$9$

$,$ A

i

is distinct.

$1$

B

i

$1$

$0$

$9$

$1$B

i

$10$

$9$

The sum of

N

N over all test cases does not exceed

$2$

$1$

$0$

$5$

$210$

$5$

$.$

Sample $1$:

Input

Output

$4$

$2$

$14$

$12$

$3$

$175$

$132$

$4$

$34812$

$1245$

$2$

$1000000000999999999$

$999999999999999998$

$2$

$2$

$3$

$1$

Explanation:

Test case

$1$

$1$: The first ball reaches the hole in

$1$

$1$ second, and the second ball reaches in

$2$

$2$ seconds. Since they do not collide at any point, both balls will reach the hole separately.

Test case

$2$

$2$: The second and third balls collide midway. As a result, only two balls will reach the hole.

Test case

$3$

$3$: The first and second balls collide midway. After this, no further collisions occur. Thus, three balls reach the hole.

Did you like the problem statement?

$19$ users found this helpful

More Info

Time limit$1$ secs

Memory limit$1\mathrm{.}5$ GB

Source Limit$50000$ Bytes