B. Петя и делители
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Маленький Петя любит искать делители у чисел. Однажды Петя столкнулся со следующей задачей.

Дано n запросов вида «xi yi». Для каждого запроса Пете нужно посчитать, сколько существует делителей числа xi, которые не делят ни одно из чисел xi - yi, xi - yi + 1, ..., xi - 1. Помогите ему.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105). В каждой из последующих n строк через пробел записано по два целых числа xi и yi (1 ≤ xi ≤ 105, 0 ≤ yi ≤ i - 1, где i — порядковый номер запроса, нумерация начинается с 1).

Ответом на запрос, для которого yi = 0, является количество делителей числа xi, при этом предыдущие числа x учитывать не следует.

Выходные данные

Для каждого запроса выведите ответ в отдельной строке: количество таких положительных целых чисел 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