[HNOI2016] 大数

小 B 有一个很大的数 $S$，长度达到了 $n$ 位；这个数可以看成是一个数字串，它可能有前导 $0$，例如 `00009312345`。小 B 还有一个素数 $p$。现在，小 B 提出了 $m$ 个询问，每个询问求 $S$ 的一个子串中有多少子串是 $p$ 的倍数（$0$ 也是 $p$ 的倍数）。例如 $S$ 为 `0077` 时，其子串 `007` 有 $6$ 个子串：`0,0,7,00,07,007`；显然 `0077` 的子串 `007` 有 $6$ 个子串都是素数 $7$ 的倍数。

第一行一个整数：$p$。 第二行一个数字串：$S$。 第三行一个整数：$m$。接下来 $m$ 行，每行两个整数 $fr,to$，表示对 $S$ 的子串 $S[fr\dots to]$ 的一次询问。注意：$S$ 的最左端的数字的位置序号为 $1$；例如 $S$ 为 `213567`，则 $S[1\dots 3]$ 为 `213`。

输出 $m$ 行，每行一个整数，第 $i$ 行是第 $i$ 个询问的答案。

11
121121
3
1 6
1 5
1 4

5
3
2
//第一个询问问的是整个串，满足条件的子串分别有：121121,2112,11,121,121。

#### 样例 1 解释 第一个询问问的是整个串，满足条件的子串分别有：`121121,2112,11,121,121`。 #### 数据范围 对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$，$2\le p\le 10^9$，$S$ 中只有数字字符，$p$ 为素数。