题目描述

小 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…to]$ 的一次询问。注意：$S$ 的最左端的数字的位置序号为 $1$；例如 $S$ 为 213567，则 $S[1]$ 为 2，$S[1…3]$ 为 213。

数据范围

$N,M \le 100000$，$P$ 为素数 。

输出格式

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

样例

11 
121121 
3 
1 6 
1 5 
1 4 

5
3
2

样例 1 解释

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

提示

2016.4.19 新加数据一组

题目来源

没有写明来源