[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$ 个询问的答案。

输入输出样例

输入样例 #1

11
121121
3
1 6
1 5
1 4

输出样例 #1

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$ 为素数。