Bytie 小男孩必须背诵一首诗的片段。这首诗遵循现代艺术的最佳风格，是一个仅由小写英文字母组成的长字符串。显然，它听起来很糟糕，但这并不是 Bytie 最担心的问题。最重要的是，他完全忘记了自己应该背诵哪一个片段。而且它们看起来都很难记忆……

然而，还是有希望的：诗歌的某些部分表现出一定的规律性。特别地，有时一个片段（设为 $A$）只是另一个片段（设为 $B$）的多次重复（换句话说，$A=BB\dots B$，即 $A=B^k$，其中 $k \ge 1$ 是一个整数）。在这种情况下，我们称 $B$ 是 $A$ 的一个完全周期（特别地，每个字符串都是其自身的完全周期）。如果给定的片段有一个较短的完全周期，Bytie 的任务就会变得简单。问题仍然是……那个片段到底是哪一个？

请为 Bytie 提供帮助——编写一个程序，读取整首诗以及 Bytie 怀疑他应该背诵的片段列表，并为每一个片段确定其最短的完全周期长度。

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 500,000$)。第二行包含一个长度为 $n$ 的字符串，由小写英文字母组成，即这首诗。我们将字符的位置从 $1$ 到 $n$ 编号。

下一行包含一个整数 $q$ ($1 \le q \le 2,000,000$)，表示片段的数量。接下来的 $q$ 行给出查询，每行一个。每个查询包含一对整数 $a_i$ 和 $b_i$ ($1 \le a_i \le b_i \le n$)，由单个空格分隔，要求输出从位置 $a_i$ 开始到位置 $b_i$ 结束的诗歌片段的最短完全周期长度。

在总分占比 42% 的测试点中，额外满足 $n \le 10,000$。其中一些测试点（总分占比 30%）还满足 $q \le 10,000$。

输出格式

程序应在标准输出中打印 $q$ 行。第 $i$ 行应包含一个整数，即第 $i$ 个查询的答案。

样例

输入 1

8
aaabcabc
3
1 3
3 8
4 8

输出 1

1
3
5