题目描述

某年某月某日，T64打开了某个无聊的密码网站。   作为一个热衷于破译密码的SB，T64的IQ是非常高的，但是，一个人是无法在 一瞬间完成无数份密码的破译工作的（也许两瞬间），所以这个任务就交给你和 他共同来完成。   一个密码对应一个字符串（仅包含小写英文字母），令这个串为S。你成功地 破解了这个密码串，当且仅当你找到了一个最短的T，使得S=T^K，即T重复K次。 密码S的关键值即为T的长度。   这个网站的密码有一个特性，它是一个很长很长的母密码的一段，碰巧的是，你无意当中窃取到了这个密码串。作为一台十分负责的计算机，请帮助T64解 决这个问题。

输入格式

m+3行。第一行为正整数n，第二行为一个长为n的字符串s。第三行为一个正整数m，表示密码串的个数。第四至m+3行每行两个正整数L，R(L≤R)，表示询问的密码串在母密码串中的位置。

输出格式

共m行。每一行一个正整数，表示对应密码串的关键值。

6
aababa
3
1  3
1  2
2  6

3
1   
5

   

提示

20  x≤ 500000,y≤ 2000000

题目来源

没有写明来源