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

문제

Назовём индексом примечательности цифровой строки $SS$ для заданного простого числа $PP$ число различных пар позиций $i,ji,j$ ($1\le i\le j\le \mathrm{\mid }S\mathrm{\mid }1\; \backslash le\; i\; \backslash le\; j\; \backslash le\; |S|$), для которых число, образованное цифрами, идущими в строке $SS$ подряд  c $ii$-й по $jj$-ю позицию включительно, делится на $PP$. Число с ведущими нулями считается равным соответствующему числу без ведущих нулей. 

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

Задана цифровая строка $TT$ и простое число $PP$. Tребуется ответить на $qq$ запросов вида <<найти индекс примечательности для подстроки $TT$ с позиции $ll$ по позицию $rr$ включительно>>.

입력

Первая строка содержит одно простое число $PP$ ($2\le P\le {10}^9+72\; \backslash le\; P\; \backslash le\; 10^9+7$). Вторая строка содержит цифровую строку $TT$ ($1\le \mathrm{\mid }T\mathrm{\mid }\le {10}^{5}1\; \backslash le\; |T|\; \backslash le\; 10^5$). Третья строка содержит одно целое число $qq$ --- число запросов ($1\le q\le {10}^{5}1\; \backslash le\; q\; \backslash le\; 10^5$).

Каждая из последующих $qq$ строк задаёт один запрос и содержит два целых числа $ll$ и $rr$ --- левую и правую границу подстроки, индекс примечательности которой интересует ($1\le l\le r\le \mathrm{\mid }T\mathrm{\mid }1\; \backslash le\; l\; \backslash le\; r\; \backslash le\; |T|$). 

출력

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