题目描述

对于给定的质数 $P$，定义数字串 $S$ 的显著性指数为满足下列条件的不同位置对 $(i,j)$ 的数量：

$$1\le i\le j\le |S|,$$

并且由 $S$ 中第 $i$ 位到第 $j$ 位连续数字组成的整数能够被 $P$ 整除。

带有前导零的数字按去掉前导零后的普通整数理解。

例如，对于字符串 070070 和 $P=13$，满足条件的位置对为：

$$(1,1),(1,5),(1,6),(2,5),(2,6),(3,3),(3,4),(4,4),(6,6).$$

因此它的显著性指数为 $9$。

现在给定一个数字串 $T$ 和质数 $P$。你需要回答 $q$ 个询问：求子串 $T[l\ldots r]$ 的显著性指数。

输入格式

第一行包含一个质数 $P$：

$$2\le P\le 10^9+7.$$

第二行包含数字串 $T$：

$$1\le |T|\le 10^5.$$

第三行包含一个整数 $q$，表示询问数：

$$1\le q\le 10^5.$$

接下来 $q$ 行，每行两个整数 $l,r$，表示询问子串的左右端点：

$$1\le l\le r\le |T|.$$

输出格式

对于每个询问，单独输出一行一个整数，表示相应子串的显著性指数。

样例

13
070070
3
1 6
2 5
2 2

9
4
0