好的，这是整理好的题面，格式清晰。

题目描述

给出一个由小写英文字母组成的字符串 ( S )，再给出 ( q ) 个询问。
每个询问给出两个整数 ( a, b )，要求回答 ( S[a..b] )（子串）的最短循环节长度。

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

输入格式

第一行一个正整数 ( n )，表示 ( S ) 的长度。
第二行 ( n ) 个小写英文字母，表示字符串 ( S )。
第三行一个正整数 ( q )，表示询问个数。
接下来 ( q ) 行，每行两个正整数 ( a, b )，表示询问子串 ( S[a..b] ) 的最短循环节长度（下标从 1 开始）。

输出格式

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

数据范围

• ( 1 \le a \le b \le n \le 5\times 10^5 )
• ( q \le 2\times 10^6 )

输入样例

8
aaabcabc
3
1 3
3 8
4 8

输出样例

1
3
5

样例解释

字符串 ( S = \text{"aaabcabc"} )（长度 8）。

询问 1

( a=1, b=3 )，子串 "aaa"
最短循环节是 "a"，长度 1。
输出 1。

询问 2

( a=3, b=8 )，子串 "abcabc"
最短循环节是 "abc"，长度 3（因为 "abcabc" 可以由 "abc" 重复 2 次得到）。
输出 3。

询问 3

( a=4, b=8 )，子串 "bcabc"
最短循环节是它本身，因为不能由更短的串重复得到，长度 = 子串长度 = 5。
输出 5。