#2696. 「POI2012」可怕的诗 A Horrible Poem

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定由小写英文字母组成的字符串 S ,有 q 个询问,每次询问给定 S 的一个子串,求其最短循环节。

如果字符串 A 可以由字符串 B 重复若干次得到,则字符串 B 是字符串 A 的一个循环节。

输入格式

第一行一个正整数 n (n \le 500\ 000) ,表示字符串 S 的长度。

接下来一行 n 个小写英文字母,表示字符串 S .

接下来一行一个正整数 q (q \le 2\ 000\ 000) ,表示询问个数。

接下来 q 行每行两个正整数 a,b (1 \le a \le b \le n) ,表示询问字符串 S 从第 a 个字母到第 b 个字母组成的子串的最短循环节长度。

输出格式

输出 q 行,每行一个正整数,表示询问的答案。

样例

样例输入

8
aaabcabc
3
1 3
3 8
4 8

样例输出

1
3
5