Description

Xiao B has a very large number $S$ of length $n$; this number can be regarded as a string of digits and may have leading $0$s, for example, 00009312345. Xiao B also has a prime $p$. Now, Xiao B proposes $m$ queries. For each query, within a substring of $S$, count how many of its substrings are multiples of $p$ ($0$ is also considered a multiple of $p$). For example, when $S$ is 0077, its substring 007 has $6$ substrings: 0,0,7,00,07,007; clearly, all $6$ substrings of 007 are multiples of the prime $7$.

Input Format

The first line contains an integer $p$.

The second line contains a digit string $S$.

The third line contains an integer $m$. Then $m$ lines follow, each containing two integers $fr, to$, representing a query on the substring $S[fr\dots to]$ of $S$. Note: the leftmost digit of $S$ has index $1$; for example, if $S$ is 213567, then $S[1\dots 3]$ is 213.

Output Format

Output $m$ lines, each containing one integer. The $i$-th line is the answer to the $i$-th query.

11
121121
3
1 6
1 5
1 4

5
3
2

Hint

Sample 1 Explanation

The first query asks about the entire string. The substrings that satisfy the condition are: 121121,2112,11,121,121.

Constraints

For $100\%$ of the testdata, $1\le n,m\le 2\times 10^5$, $2\le p\le 10^9$, $S$ contains only digit characters, and $p$ is prime.

Translated by ChatGPT 5