题目描述

小 Petya 喜欢研究数的约数。一天，Petya 碰到了下面这个问题：

给你 $n$ 个形如 "$x_i$ $y_i$" 的询问。对每个询问，Petya 要统计 $x_i$ 的约数中有多少个不能整除 $x_{i-y_i}, x_{i-y_i+1}, \ldots, x_{i-1}$ 中的任何一个数。请帮帮他。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^5$）。接下来 $n$ 行，每行两个用空格隔开的整数 $x_i$ 和 $y_i$（$1 \le x_i \le 10^5$，$0 \le y_i \le i-1$，其中 $i$ 是询问的序号，从 1 开始编号）。

若某询问的 $y_i = 0$，则该询问的答案就是 $x_i$ 的约数个数，此时无需考虑之前的任何 $x$。

输出格式

对每个询问输出一行答案：满足 $k \mid x_i$ 且对所有 $j$（$i - y_i \le j \lt i$）都有 $k \nmid x_j$ 的正整数 $k$ 的个数。

6
4 0
3 1
5 2
6 2
18 4
10000 3

3
1
1
2
2
22

说明/提示

前 5 个询问的答案对应的约数如下：

1. 1, 2, 4
2. 3
3. 5
4. 2, 6
5. 9, 18