题目描述

原题来自：POI 2012

给出一个由小写英文字母组成的字符串 $\red{S}$，再给出 $\red{q}$ 个询问，要求回答 $\red{S}$ 某个子串的最短循环节。

如果字符串 $\red{B}$ 是字符串 $\red{A}$ 的循环节，那么 $\red{A}$ 可以由 $\red{B}$ 重复若干次得到。

输入格式

第一行一个正整数 $\red{n}$，表示 $\red{S}$ 的长度。

第二行 $\red{n}$ 个小写英文字母，表示字符串 $\red{S}$ 。

第三行一个正整数 $\red{q}$ ，表示询问个数。 下面 $\red{q}$ 行每行两个正整数$\red{ a,b}$ ，表示询问字符串 $\red{S[a..b]}$的最短循环节长度。

输出格式

依次输出 $\red{q}$ 行正整数，第 $\red{i}$ 行的正整数对应第 $\red{i}$ 个询问的答案。

样例

输入样例

8
aaabcabc
3
1 3
3 8
4 8

输出样例

1
3
5

提示

$\red{1 \le a \le b \le n \le {5\times 10^5} , q \le {2\times 10 ^ 6}}$。