题目背景

众所周知，一场比赛需要有 $\geq 1$ 道套路题，用于考察选手的知识储备。

但实际上，这道题不需要什么知识储备，但还是很套路。一般这种题，我们称之为“好题”。所以欢迎大家来做这道好题 （?） 。

题目描述

定义：若字符串 $\rm S$ 可以由若干个相同的字符串 $T$ 依次连接得到，则可以称 $T$ 是$\rm S$ 的一个循环节。

例如 :

• abc 是 abcabc 的循环节。
• ABA 不是 ABABA 的循环节。
• ttt 是 ttttttttt 的循环节。

显然，有的字符串可以存在多个循环节。例如 aaaaaa 的循环节可以是a、aa、aaa。

现在给你一个字符串 $\rm S$ 以及 $q$ 个询问。每个询问会通过区间的形式来指定 $\rm S$ 的一个子串，请你为这个子串寻找循环节，并输出其中最短那个的长度。

输入格式

第 $1$ 行共一个正整数 $n$，表示字符串 $\rm S$ 的长度。

第 $2$ 行共一个长度为 $n$ 且仅有小写英文字母的字符串 $\rm S$。

第 $3$ 行共一个正整数 $q$，表示询问个数。

第 $4\sim q+3$ 行，每行包含两个正整数 $l, r$，表示询问子串 $\mathrm{S}[l \sim r]$ 的循环节的最短长度。

注意：本题约定字符串的下标由 $1$ 开始编号。

输出格式

输出共 $q$ 行，每行一个整数表示答案。

样例 #1

样例输入 #1

8
aaabcabc
4
3 8
4 8
1 3
1 8

样例输出 #1

3
5
1
8

样例输入 #2

72
abababcabababcabababcabababcabababcabababcabababcabababcabababababababab
8
1 6
8 13
15 20
1 21
1 56
8 56
1 55
57 72

样例输出 #2

2
2
2
7
7
7
55
2

提示

对于前 $20\%$ 的数据，保证 $1\leq n,q\leq 20$ 。

对于前 $40\%$ 的数据，保证 $1\leq n,q\leq 10^4$。

对于前 $65\%$ 的数据，保证 $1\leq n,q \leq 10^5$。

对于全部 $100 \%$ 的数据，保证 $1 \le n \le 5 \times 10^5$，$1 \le q \le 2 \times 10^6$，$1 \le l \le r \le n$。