给定由小写英文字母组成的字符串 ，有 个询问，每次询问给定 的一个子串，求其最短整循环节。
如果字符串 可以由字符串 重复若干次得到，则字符串 是字符串 的一个整循环节（即 ）。
第一行一个正整数 ，表示字符串 的长度。
接下来一行 个小写英文字母，表示字符串 .
接下来一行一个正整数 ，表示询问个数。
接下来 行每行两个正整数 ，表示询问字符串 从第 个字母到第 个字母组成的子串的最短循环节长度。
输出 行，每行一个正整数，表示询问的答案。
8 aaabcabc 3 1 3 3 8 4 8
1 3 5