密码破译

时间限制:40s      空间限制:128MB

题目描述

  某年某月某日,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 


题目来源

没有写明来源