Маленький Петя любит искать делители у чисел. Однажды Петя столкнулся со следующей задачей.
Дано 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, что
Выпишем делители, которые дают ответ для первых 5 запросов:
1) 1, 2, 4
2) 3
3) 5
4) 2, 6
5) 9, 18
6 4 0 3 1 5 2 6 2 18 4 10000 3
3 1 1 2 2 22
5000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач