Description

Byteie 男孩需要背诵一首诗的某个片段。这首诗遵循现代艺术的最高标准，是一个仅由小写英文字母组成的长字符串。显然，它听起来很糟糕，但这还不是 Byteie 最担心的。首先，他完全忘记了自己该背诵哪个片段。而且所有片段看起来都很难记……

不过仍有希望：诗中某些部分呈现出特定的规律性。特别是，时常会出现某个片段（记作 $A$）仅是另一个片段（记作 $B$）的多次重复（即 $A = BB\cdots B$，可表示为 $A = B^k$，其中 $k\geq1$ 为整数）。这种情况下，我们称 $B$ 是 $A$ 的一个完整周期（特别地，每个字符串都是其自身的完整周期）。如果一个片段存在很短的完整周期，Byteie 的任务就会变得简单。问题在于……到底是哪个片段呢？

送给 Byteie 一份礼物吧——编写一个程序，它会读入整首诗以及 Byteie 怀疑可能需要背诵的片段列表，并针对每个片段找出其最短的完整周期

Input Format

第一行：一个整数 $n$ ($1\leq n\leq500,000$)，表示诗的长度。

第二行：一个长度为 $n$ 的字符串，表示诗的内容。字符串中字符的位置依次编号为 $1$ 到 $n$。

第三行：一个整数 $q$ ($1\leq q\leq2,000,000$)，表示查询的片段数量。

接下来的 $q$ 行：每行包含两个整数 $a_i$ 和 $b_i$ ($1\leq a_i\leq b_i\leq n$)，用空格分隔。表示查询从位置 $a_i$ 开始到位置 $b_i$ 结束的诗的片段的最短完整周期的长度。

在总计占比 $42\%$ 分数的测试点中，额外满足 $n\leq10,000$。其中占比 $30\%$ 分数的测试点还满足 $q\leq10,000$。

Output Format

输出 $q$ 行到标准输出。第 $i$ 行输出一个整数，表示第 $i$ 个查询的答案。

8
aaabcabc
3
1 3
3 8
4 8

1
3
5

Hint

题面翻译由 deepseek-R1 提供。