题目描述

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