Problem Description

You are given a string \( S \). There are \( q \) queries, each providing a pair \( (i, k )\). For each query, determine how many non-empty strings \( A \) exist such that there are non-empty strings \( B_1, B_2, \ldots, B_{k-1} \) satisfying:

\[ S[1, i] = A B_1 A B_2 A \ldots A B_{k-1} A \]

where \( S[1, i] \) denotes the prefix of \( S \) of length \( i \).

Input Format

The first line contains a positive integer \( n \), representing the length of \( S \).

The next line contains a string of length \( n \) consisting only of lowercase letters, representing \( S \).

The next line contains a positive integer \( q \), representing the number of queries.

The following \( q \) lines each contain two positive integers \( i \) and \( k \), representing a query.

Output Format

Output \( q \) lines, each containing a non-negative integer representing the answer to the corresponding query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
2
1
2
1

Sample Input #2

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

Sample Output #2

1
1
1
0
0
2
1
1
0
1

Notes

[Sample Explanation #1]

For the first query \( (5, 3) \), you can take \( A = \texttt{a} \), \( B_1 = \varepsilon \), \( B_2 = \texttt{ba} \), where \( \varepsilon \) represents the empty string. It can be proven that there is exactly one valid \( A \).

[Data Range]

This problem uses subtask testing.

For \( 100\% \) of the data: \( 1 \leq k \leq i \leq n \leq 2 \times 10^5 \), \( 1 \leq q \leq 2 \times 10^5 \), \( s \) consists only of lowercase letters.

见题面 Input 部分

见题面 Output 部分