给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

第一行一个正整数n (n<=500,000)，表示S的长度。
第二行n个小写英文字母，表示字符串S。
第三行一个正整数q (q<=2,000,000)，表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n)，表示询问字符串S[a..b]的最短循环节长度。

依次输出q行正整数，第i行的正整数对应第i个询问的答案。

8
aaabcabc
3
1 3
3 8
4 8

1
3
5

 #include<cstring>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #define G 29

 #define N 500007

 #define mod 1000000007

 #define ll long long

 #define Wb putchar(' ')

 #define We putchar('\n')

 #define rg register int

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 inline void write(int x)

 {

     if(x<) putchar('-'),x=-x;

     if (x==) putchar();

     int num=;char c[];

     while(x) c[++num]=(x%)+,x/=;

     while(num) putchar(c[num--]);

 }

 int n,Q;

 char ch[N];

 ll bin[N],hash[N];

 bool flag[N];

 vector<int>ve[N];

 void init_prime()

 {

     for (rg i=;i<=n;i++)

         if (!flag[i])

         {

             rg x=i;

             while(x<=n)

             {

                 int z=x;

                 while(z%i==) ve[x].push_back(i),z/=i;

                 flag[x]=true;

                 x+=i;

             }

         }

 }

 bool judge(int x,int l,int r)

 {

     ll res1=hash[r-x]-(hash[l-]*bin[(r-x)-l+])%mod;

     ll res2=hash[r]-(hash[l+x-]*bin[(r-x)-l+])%mod;

     res1=(res1%mod+mod)%mod,res2=(res2%mod+mod)%mod;

     return res1==res2;

 }

 int main()

 {

     n=read(),scanf("%s",ch+),bin[]=,init_prime();

     for (int i=;i<=n;i++)

         hash[i]=(hash[i-]*G+ch[i]-'a')%mod,bin[i]=(bin[i-]*G)%mod;

     Q=read();

     while(Q--)

     {

         int l=read(),r=read(),num=r-l+,ans=num;

         if (num==) write(),We;

         else

         {

             for (rg i=;i<ve[num].size();i++)

                 if (judge(ans/ve[num][i],l,r)) ans/=ve[num][i];

             write(ans),We;

         }

     }

 }