Given a string $S$ and $q$ queries of the form $l,r$, find the length of the shortest string that, when repeated some number of times, exactly forms the substring $S[l…r]$.

Input

• The first line contains the string $S$.
• The second line contains an integer $q$.
• The next $q$ lines each contain two integers $l$ and $r$.

Output

• Print $q$ integers, each being the answer to the corresponding query.

Constraints

• $1 \le |S| \le 5 \times 10^5$.
• $1 \le q \le 10^6$.

Example

Input:

8
aaabcabc
3
1 3
3 8
4 8

Output:

1
3
5

Explanation:

• Query 1: Repeating the string a three times results in the string aaa.
• Query 2: Repeating the string abc two times results in the string abcabc.
• Query 3: Repeating the string abcab one time results in the string abcab.