样例下载

题目描述

老师在黑板上随手写了一个整数 $P$。小明惊奇地发现， $P$ 恰好是一个质数。

然后老师又随手写了一个仅由阿拉伯数字组成的字符串 $S$。注意：$S$ 可能有若干个前导零。

现在，老师让小明回答 $T$ 个问题：

每个问题给出两个整数 $L, R$，小明需要回答 $S[L...R]$ 有多少个子串可以被 $P$ 整除？

注意：$S[L...R]$ 表示字符串 $S$ 的第 $L$ 个至第 $R$ 个字符组成的字符串。字符串 $S$ 第一个字符下标为 $1$。所谓子串能被 $P$ 整除，是指该子串所表示的整数能被 $P$ 整除。

输入格式

第一行：包含一个整数 $P$，数据保证 $P$ 是质数。

第二行：包含一个字符串 $S$，数据保证 $S$ 仅包含阿拉伯数字。

第三行：包含一个整数：$T$。

接下来 $T$ 行，每行两个整数 $L,R$。

输出格式

共 $T$ 行，每个问题的答案占一行。

输入样例

3
0012
2
1 4
2 4

输出样例

6
3

样例解释

第一个问题：

$S[1...4]$ = 0012, 满足条件的子串有 $6$ 个，分别为：0, 0, 00, 12, 012, 0012

第二个问题：

$S[2...4]$ = 012, 满足条件的子串有 $3$ 个，分别为：0, 12, 012

数据范围

$100\%$ 的数据，$1 ≤ |S|, T ≤ 2 × 10^5, 2 ≤ P ≤ 10^9, 1 ≤ L ≤ R ≤ |S|$。其中 $|S|$ 表示字符串 $S$ 包含的字符个数。