4082: 「HNOI2016」大数

小 B 有一个很大的数 $ S $，长度达到了 $ N $ 位；这个数可以看成是一个串，它可能有前导 $ 0 $，例如 ``00009312345`` 。小 B 还有一个素数 $ P $。 现在，小 B 提出了 $ M $ 个询问，每个询问求 $ S $ 的一个子串中有多少子串是 $ P $ 的倍数（$ 0 $ 也是 $ P $ 的倍数）。例如 $ S $ 为 ``0077`` 时，其子串 ``007 `` 有六个子串：``0``, ``0``, ``7``, ``00``, ``07``, ``007``；显然 ``0077`` 的子串 ``077`` 的六个子串都是素数 $ 7 $ 的倍数。

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

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

11
121121
3
1 6
1 5
1 4

5
3
2