Description

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

Input

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

Output

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

Sample Input

Sample Output

Hint

 20  x≤ 500000,y≤ 2000000 

Source