地雷布置在一条直线上。只要其中任意一枚发生爆炸，所有位于其杀伤半径内的地雷也会随之爆炸。请确定：对于每一枚地雷，如果我们“手动”引爆它，会有多少枚地雷发生爆炸。

输入格式

第一行输入包含一个正整数 $z$ —— 数据集的数量。接下来依次给出各个数据集，格式如下：

每个数据集的第一行包含地雷数量 $n$（$1 \le n \le 100{,}000$）。接下来的 $n$ 行中，每行包含两个整数 $x_i, r_i$（$|x_i| \le 10^{18}$，$0 \le r_i \le 2 \cdot 10^{18}$），分别表示第 $i$ 个地雷的位置和杀伤半径。地雷按位置 $x$ 递增顺序给出。任意两枚地雷不会位于同一位置。地雷的作用范围也包括与其距离恰好等于其杀伤半径的地雷。

输出格式

对于每个数据集，在一行中输出 $n$ 个整数 $c_1,\ldots,c_n$，其中 $c_i$ 表示当手动引爆第 $i$ 枚地雷时会爆炸的地雷数量（包括第 $i$ 枚地雷本身）。

样例数据

对于输入数据：

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

正确输出为：

4 3 3 3 4