Na prostej leżą miny przeciwpancerne. W razie wybuchu którejkolwiek z nich, wszystkie miny znajdujące się w jej promieniu rażenia również wybuchną. Określ, dla każdej z min, ile min wybuchnie, gdy tę jedną zdetonujemy "ręcznie".

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą dodatnią $z$ - liczbę zestawów danych. Potem kolejno podawane są zestawy w następującej postaci:

Pierwszy wiersz opisu zestawu zawiera liczbę min $n$ ($1 \le n \le 100,000$). W kolejnych $n$ wierszach znajdują się po dwie liczby całkowite $x_i, r_i$ ($|x_i| \le 10^{18}$, $0 \le r_i \le 2 \cdot 10^{18}$) - odpowiednio położenie i promień rażenia $i$-tej miny. Miny podane są w kolejności rosnącego położenia $x$. Żadne dwie miny nie leżą w jednym miejscu. Zasięg miny obejmuje również miny w odległości równej jej promieniowi rażenia.

Wyjście

Dla każdego zestawu danych wypisz (w pojedynczym wierszu) $n$ liczb całkowitych $c_1,\ldots,c_n$, gdzie $c_i$ oznacza liczbę min, które wybuchną przy zdetonowaniu $i$-tej miny (wliczając samą $i$-tą minę).

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

4 3 3 3 4