Индекс примечательности

Назовём индексом примечательности цифровой строки $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|$).

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