24635번 - Индекс примечательности 다국어

문제

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

출력

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

제한

힌트