Дан массив a из n элементов, все элементы — натуральные числа, не превышающие n.
Необходимо обработать q запросов к этому массиву. Каждый запрос задаётся двумя числами p и k. Запрос состоит из нескольких операций, каждая операция заменяет число p числом p + ap + k. Эти операции проводятся, пока p не станет больше, чем n. Для каждого запроса необходимо выяснить количество таких операций.
Выходные данные
Выведите q чисел, i-е из них должно быть равно ответу на запрос под номером i.
Примечание
Разберём пример из условия:
В первом запросе после первой операции p = 3, после второй p = 5.
Во втором и третьем запросах p становится больше n уже после первой операции.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1 1
3
1 1
2 1
3 1
|
2
1
1
|