주목도 지수

숫자 문자열 $S$와 주어진 소수 $P$에 대해 주목도 지수를 다음과 같이 정의한다. $1 \le i \le j \le |S|$인 위치 쌍 $i,j$ 가운데, $S$의 $i$번째부터 $j$번째까지의 숫자를 순서대로 이어 붙여 만든 수가 $P$로 나누어떨어지는 쌍의 개수이다. 앞에 0이 붙은 수는 앞의 0을 뺀 수와 같은 것으로 본다.

예를 들어 문자열 070070과 $P=13$에 대해 조건을 만족하는 쌍은 $(1,1)$, $(1,5)$, $(1,6)$, $(2,5)$, $(2,6)$, $(3,3)$, $(3,4)$, $(4,4)$, $(6,6)$이다. 따라서 이 문자열의 주목도 지수는 9이다.

숫자 문자열 $T$와 소수 $P$가 주어진다. $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|$).

각 질의마다 해당 부분 문자열의 주목도 지수를 한 줄에 하나씩 정수로 출력한다.