You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小熊玩偶

商店有26种不同颜色的小熊玩偶，分别用$26$个小写英文字母表示，店家将$n$只小熊排列成一行。 小明想知道小熊排列的某一个子段是否有可能由规模更小的子段通过重复若干次得到。 请你帮小明计算该子段的最小重复子段长度，若该子段无法通过重复更小规模的子段得到，则返回1。

数据范围

• $n\le 5\times 10^5$
• $q\le 2\times 10^6$

输入格式

• 第$1$行$1$个正整数 $n$。
• 第$2$行$n$个小写英文字母表示小熊的排列。
• 第$3$行$1$个正整数 $q$，表示询问次数。
• 接下来$q$行每行两个正整数$a, b(1\le a\le b\le n)$，表示小熊排列中第$a$只到第$b$只小熊构成的$[a,b]$子段

输出格式

• $q$行，分别表示$[a,b]$子段的最小重复子段长度

样例输入 #1

8
aaabcabc
3
1 3
3 8
4 8

样例输出 #1

1
3
5