Anti-tank mines are placed on a straight line. In the event that any one of them explodes, all mines within its blast radius will also explode. Determine, for each mine, how many mines will explode if we manually detonate that single mine.

Input

The first line of the input contains a positive integer $z$ — the number of test cases. Then the test cases follow in the format below:

The first line of each test case contains the number of mines $n$ ($1 \le n \le 100{,}000$). In the next $n$ lines there are two integers $x_i, r_i$ ($|x_i| \le 10^{18}$, $0 \le r_i \le 2 \cdot 10^{18}$) — the position and blast radius of the $i$-th mine, respectively. The mines are given in increasing order of position $x$. No two mines share the same position. The range of a mine also includes mines at distance exactly equal to its blast radius.

Output

For each test case, print (in a single line) $n$ integers $c_1,\ldots,c_n$, where $c_i$ is the number of mines that will explode when detonating the $i$-th mine (including the $i$-th mine itself).

Example

For the input:

1
5
0 2
2 1
3 2
4 1
6 2

the correct output is:

4 3 3 3 4