Маленький Петя любит искать делители у чисел. Однажды Петя столкнулся со следующей задачей.
Дано 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
| Codeforces Beta Round 85 (Div. 1 Only) |
|---|
| Закончено |
