题目描述

Bytie boy has to learn a fragment of a certain poem by heart. The poem, following the best lines of modern art, is a long string consisting of lowercase English alphabet letters only. Obviously, it sounds horrible, but that is the least of Bytie's worries.

First and foremost, he completely forgot which fragment is he supposed to learn. And they all look quite difficult to memorize...

There is hope, however: some parts of the poem exhibit certain regularity. In particular, every now and then a fragment, say , is but a multiple repetition of another fragment, say (in other words, , i.e., , where is an integer). In such case we say that is a full period of (in particular, every string is its own full period).

If a given fragment has a short full period, Bytie's task will be easy. The question remains... which fragment was that?

Make a gift for Bytie - write a program that will read the whole poem as well as a list of fragments that Bytie suspects might be the one he is supposed to memorize, and for each of them determines its shortest full period.

输入格式

In the first line of the standard input there is a single integer ().

In the second line there is a string of length consisting of lowercase English alphabet letters-the poem.

We number the positions of its successive characters from 1 to .

The next line holds a single integer () denoting the number of fragments.

Then the following lines give queries, one per line.

Each query is a pair of integers and (), separated by a single space, such that the answer to the query should be the length of the shortest full period of the poem's fragment that begins at position and ends at position .

In tests worth in total 42% of the points holds in addition.

In some of those, worth 30% of points in total, holds as well.

输出格式

Your program should print lines on the standard output.

The -th of these lines should hold a single integer - the answer to the -th query.

题目大意

给出一个由小写英文字母组成的字符串 $S$，再给出 $q$ 个询问，要求回答 $S$ 某个子串的最短循环节。

如果字符串 $B$ 是字符串 $A$ 的循环节，那么 $A$ 可以由 $B$ 重复若干次得到。

第一行一个正整数 $n\ (n\le 5\times 10^5)$，表示 $S$ 的长度。

第二行 $n$ 个小写英文字母，表示字符串 $S$。

第三行一个正整数 $q\ (q\le 2\times 10^6)$，表示询问次数。

下面 $q$ 行每行两个正整数 $a,b(1\le a\le b\le n)$，表示询问字符串 $S[a\cdots b]$ 的最短循环节长度。

8
aaabcabc
3
1 3
3 8
4 8

1
3
5