There are $n$ balls along a number line, each ball is represented by a point on the line. Ball $i$ moves at velocity $v_i$ ($v_i \neq 0$) along this number line and is initially at point $x_i$.

When two balls collide (occupy the same point along the number line), their velocities switch. For example, if ball $i$ with velocity $2$ collides with ball $j$ with velocity $-3$, ball $i$ will have velocity $-3$ and ball $j$ will have velocity $2$ after the collision.

Given each ball's initial distinct position and velocity, find for each ball $i$ the sum of the floor of the times that ball $i$ collides with another ball. Formally, ball $i$ collides with another ball $k$ times in total at times $t_1, t_2, \ldots t_k$. Print, $\sum_{i=1}^k \lfloor t_i \rfloor$ for each ball.

It is guaranteed that whenever two balls $i, j$ collide, the signs of their velocities will be different ($v_i \cdot v_j < 0$).

Input format

• The first line of the input contains a single integer $t$ denoting the number of test cases.
• The first line of each test case contains a single integer $n$ denoting the number of balls.
• The second line of each test case contains $n$ integers $x_i$ denoting the initial position of ball $i$.
• The third line of each test case contains $n$ integers $v_i$ denoting the velocity of ball $i$.

Output format

Print $n$ integers denoting the $i^{th}$ being the sum of the floors of each time ball $i$ collides with another ball.

Constraints

$1 \leq t \leq 100$

$1\leq n \leq 2000$

$|x_i| \leq 2000$

$0 < |v_i| \leq 2000$

• It is guaranteed that, in the given input, whenever two balls collide the signs of their velocities will be different.

• It is guaranteed that the sum of $n$ over all test cases is less than or equal to $2000$.

• No two pairs of balls collide at the same place at the same time.