Индекс примечательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём индексом примечательности цифровой строки $$$S$$$ для заданного простого числа $$$P$$$ число различных пар позиций $$$i,j$$$ ($$$1 \le i \le j \le |S|$$$), для которых число, образованное цифрами, идущими в строке $$$S$$$ подряд c $$$i$$$-й по $$$j$$$-ю позицию включительно, делится на $$$P$$$. Число с ведущими нулями считается равным соответствующему числу без ведущих нулей.

Например, для строки 070070 и $$$P=13$$$ соответствующие пары — $$$(1,1)$$$, $$$(1,5)$$$, $$$(1,6)$$$, $$$(2,5)$$$, $$$(2,6)$$$, $$$(3,3)$$$, $$$(3,4)$$$, $$$(4,4)$$$ и $$$(6,6)$$$. Таким образом, её индекс примечательности равен 9.

Задана цифровая строка $$$T$$$ и простое число $$$P$$$. Tребуется ответить на $$$q$$$ запросов вида «найти индекс примечательности для подстроки $$$T$$$ с позиции $$$l$$$ по позицию $$$r$$$ включительно».

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

Первая строка содержит одно простое число $$$P$$$ ($$$2 \le P \le 10^9+7$$$). Вторая строка содержит цифровую строку $$$T$$$ ($$$1 \le |T| \le 10^5$$$). Третья строка содержит одно целое число $$$q$$$ — число запросов ($$$1 \le q \le 10^5$$$).

Каждая из последующих $$$q$$$ строк задаёт один запрос и содержит два целых числа $$$l$$$ и $$$r$$$ — левую и правую границу подстроки, индекс примечательности которой интересует ($$$1 \le l \le r \le |T|$$$).

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

Для каждого запроса выведите на отдельной строке одно целое число — индекс примечательности соответствующей подстроки.

Пример

Входные данные
13
070070
3
1 6
2 5
2 2
Выходные данные
9
4
0