Description

Original source: POI 2012

Given a string $S$ consisting of lowercase English letters, and $q$ queries, each query asks for the length of the shortest cycle in a substring of $S$.

A string $B$ is a cycle of string $A$ if $A$ can be formed by repeating $B$ multiple times.

Input Format

The first line contains a positive integer $n$, the length of $S$.
The second line contains $n$ lowercase English letters, representing the string $S$.
The third line contains a positive integer $q$, the number of queries.
The following $q$ lines each contain two positive integers $a$ and $b$, representing the query for the substring $S[a..b]$ and asking for the length of its shortest cycle.

Output Format

Output $q$ lines of positive integers, where the $i$-th line corresponds to the answer for the $i$-th query.

Sample 1

8
aaabcabc
3
1 3
3 8
4 8

1
3
5

Constraints and Hints

$1 \le a \le b \le n \le {5\times 10^5} ,$ $q \le {2\times 10 ^ 6}$.