Shortest Full Period

Bytie boy has to learn a fragment of a long poem by heart. The poem is a string consisting of lowercase English letters only. Unfortunately, Bytie forgot which fragment he is supposed to memorize. There is a silver lining: some fragments of the poem exhibit a repeating pattern. A fragment S is said to have a full period T if S can be written as T repeated an integer number of times. In particular, every string is its own full period.

Your task is to help Bytie by determining the shortest full period for several fragments of the poem. For each query fragment specified by its starting and ending positions in the poem, output the length of its shortest full period.

Note: The positions are 1-indexed.

The shortest full period for a fragment of length L can be computed by finding the smallest integer p such that if we let π[L−1] be the last value of the prefix function of the fragment then p = L − π[L−1] and if L mod p = 0 then p is the answer; otherwise, the period is L.

inputFormat

The input begins with a single line containing the poem s (a non-empty string of lowercase English letters). The next line contains an integer q (number of queries). Each of the following q lines contains two integers l and r (1 ≤ l ≤ r ≤ |s|) representing the boundaries (inclusive) of a fragment of the poem.

outputFormat

For each query, output a single line containing one integer that denotes the length of the shortest full period of the specified fragment.

sample

ababab
2
1 6
2 5

2
2