#2053. 「HNOI2016」大数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 B 有一个很大的数 S S ,长度达到了 N N 位;这个数可以看成是一个串,它可能有前导 0 0 ,例如 00009312345 。小 B 还有一个素数 P P

现在,小 B 提出了 M M 个询问,每个询问求 S S 的一个子串中有多少子串是 P P 的倍数(0 0 也是 P P 的倍数)。例如 S S 0077 时,其子串 007 有六个子串:0, 0, 7, 00, 07, 007;显然 0077 的子串 077 的六个子串都是素数 7 7 的倍数。

输入格式

第一行一个整数:P P
第二行一个串:S S
第三行一个整数:M M
接下来 M M 行,每行两个整数 fr,to \text{fr}, \text{to},表示对 S S 的子串 S[frto]S[\text{fr} \ldots \text {to}] 的一次询问。
注意:S S 的最左端的数字的位置序号为 1 1 ;例如 S S 213567 213567 ,则 S[1] S[1] 2 2 S[13] S[1 \ldots 3] 213 213

输出格式

输出 M M 行,每行一个整数,第 i i 行是第 i i 个询问的答案。

样例

样例输入

11 
121121 
3 
1 6 
1 5 
1 4

样例输出

5
3
2

样例解释

第一个询问问的是整个串,满足条件的子串分别有:121121211211121121

数据范围与提示

对于所有的数据,N,M100000 N,M \leq 100000 P P 为素数。