Background

Original problem link: https://oier.team/problems/X1D.

Problem Description

You are given a string $S$. There are $q$ queries. Each query gives $(i, k)$. For each query, find how many non-empty strings $A$ exist such that there are (possibly empty) strings $B_1, B_2, \dots, B_{k-1}$ satisfying:

Here, $S[1,i]$ denotes the prefix of $S$ with length $i$.

Input Format

The first line contains a positive integer $n$, denoting the length of $S$.

The next line contains a string of length $n$ consisting only of lowercase letters, denoting $S$.

The next line contains a positive integer $q$.

The next $q$ lines each contain two positive integers, denoting a query $i, k$.

Output Format

Output $q$ lines. Each line contains a non-negative integer, denoting the answer.

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

1
2
1
2
1

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

Hint

Sample Explanation #1

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

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata: $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.

Translated by ChatGPT 5