A Horrible Poem

Bytie has to memorize a fragment of a certain poem. The poem, in the spirit of modern art, is a long string made up only of lowercase English letters. It sounds horrible, but that is the least of Bytie's worries: he has completely forgotten which fragment he is supposed to learn, and every fragment looks hard to memorize.

There is hope, however, because some parts of the poem are regular. Every now and then a fragment $A$ is simply another fragment $B$ repeated several times, that is, $A = BB\cdots B = B^k$ for some integer $k \ge 1$. In that case we say that $B$ is a full period of $A$ (in particular, every string is a full period of itself). A fragment with a short full period is easy to memorize.

Given the whole poem and the list of fragments Bytie suspects, determine, for each fragment, the length of its shortest full period.

The first line contains an integer $n$ ($1 \le n \le 500{,}000$). The second line contains a string of length $n$ consisting of lowercase English letters, the poem; its characters are numbered from $1$ to $n$.

The next line contains an integer $q$ ($1 \le q \le 2{,}000{,}000$), the number of fragments. Each of the next $q$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le b_i \le n$), separated by a single space, describing the fragment that starts at position $a_i$ and ends at position $b_i$.

Print $q$ lines. The $i$-th line should contain a single integer: the length of the shortest full period of the $i$-th fragment.