Description

给定由小写英文字母组成的字符串S，有q个询问，每次询问给定S的一个子串，求其最短循环节。

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

Input Format

第一行一个正整数n(n<=500000)，表示字符串S的长度。

接下来一行n个小写英文字母，表示字符串S.

接下来一行一个正整数 q(<=200000)，表示询问个数。

接下来q行每行两个正整数a,b(1=<a=<b=<n) ，表示询问字符串S从第a个字母到第b个字母组成的子串的最短循环节长度。

Output Format

输出q行，每行一个正整数，表示询问的答案。

Sample

样例输入：

8
aaabcabc
3
1 3
3 8
4 8

样例输出：

1
3
5