题目描述

你有一个字符串 $S$。$q$ 个询问，每次给出 $(i,k)$，求有多少个非空字符串 $A$，使得存在可空字符串 $B_1,B_2,\dots,B_{k-1}$ 满足：

其中 $S[1,i]$ 表示 $S$ 的长度为 $i$ 的前缀。

输入格式

第一行一个正整数 $n$ 表示 $S$ 的长度。

接下来一个长度为 $n$ 且仅包含小写字母的字符串表示 $S$。

接下来一行一个正整数表示 $q$。

接下来 $q$ 行，每行两个正整数表示一个询问的 $i,k$。

输出格式

输出 $q$ 行，每行一个非负整数表示答案。

样例

10
aabaacaaaa
5
5 3
5 2
6 1
10 4
10 5

1
2
1
2
1

样例 1 解释

对于第一次询问 $(5,3)$，可以取 $A=\texttt{a}$，$B_1=\varepsilon$，$B_2=\texttt{ba}$，其中 $\varepsilon$ 表示空串。可以证明有且仅有一个合法的 $A$。

10
bababababa
10
6 1
6 2
6 3
6 4
6 5
10 2
10 3
9 4
5 5
4 2

1
1
1
0
0
2
1
1
0
1

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据：$1\leq k\leq i\leq n\leq 2\times 10^5$，$1\leq q\leq 2\times 10^5$，$s$ 仅包含小写字母。