给定由小写英文字母组成的字符串 SSS，有 qqq 个询问，每次询问给定 SSS 的一个子串，求其最短整循环节。
如果字符串 AAA 可以由字符串 BBB 重复若干次得到，则字符串 BBB 是字符串 AAA 的一个整循环节（即 A=Bk,k∈Z+A = B^k, k\in \mathbb{Z_+}A=Bk,k∈Z+）。
第一行一个正整数 n(1≤n≤500 000)n (1\le n \le 500\ 000)n(1≤n≤500 000)，表示字符串 SSS 的长度。
接下来一行 nnn 个小写英文字母，表示字符串 SSS.
接下来一行一个正整数 q(1≤q≤2 000 000)q (1\le q \le 2\ 000\ 000)q(1≤q≤2 000 000)，表示询问个数。
接下来 qqq 行每行两个正整数 a,b(1≤a≤b≤n)a,b (1 \le a \le b \le n)a,b(1≤a≤b≤n)，表示询问字符串 SSS 从第 aaa 个字母到第 bbb 个字母组成的子串的最短循环节长度。
输出 qqq 行，每行一个正整数，表示询问的答案。
8 aaabcabc 3 1 3 3 8 4 8
1 3 5