#3647. 密码破译

内存限制:128 MiB 时间限制:40 Sec

题目描述

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