题目描述

给定一个长度为 $n$、仅由小写英文字母组成的字符串 $S$，有 $q$ 次询问。

每次询问给出两个整数 $a,b$，求子串 $S[a..b]$ 的最短循环节长度。如果一个字符串可以由某个字符串重复若干次得到，那么这个字符串称为它的循环节。

输入格式

第一行包含一个正整数 $n$，表示字符串 $S$ 的长度。

第二行包含字符串 $S$。

第三行包含一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行包含两个正整数 $a,b$，表示询问子串 $S[a..b]$。

输出格式

对于每次询问，输出一行一个整数，表示对应子串的最短循环节长度。

样例

8
aaabcabc
3
1 3
3 8
4 8

1
3
5

数据范围与提示

• $1 \le a \le b \le n \le 5 \times 10^5$
• $1 \le q \le 2 \times 10^6$

来源

一本通 2.1 练习 4，POI 2012