# include<iostream># include<cstdio># include<cstring># include<algorithm>using namespace std;const int N=1000;int n,m;char s[N+5];int cnt[N+5],SA[N+5];int rk[N+5],tSA[N+5];int height[N+5];int ans[N+5][N+5];void in(int &x){	x=0;	char c=getchar();	while(c<‘0‘||c>‘9‘){		c=getchar();	}	x=c-‘0‘;	while(c=getchar()){		if(c<‘0‘||c>‘9‘) break;		x=x*10+c-‘0‘;	}}void out(int x){	if(x>=10)		out(x/10);	putchar(x%10+‘0‘);}bool same(int *y,int i,int j,int k){	if(y[SA[i]]!=y[SA[j]]) return false;	if(SA[i]+k>=n&&SA[j]+k>=n) return true;	if(SA[i]+k<n&&SA[j]+k>=n) return false;	if(SA[i]+k>=n&&SA[j]+k<n) return false;	return y[SA[i]+k]==y[SA[j]+k];}void buildSA(){	m=130;	int *x=rk,*y=tSA;	for(int i=0;i<m;++i) cnt[i]=0;	for(int i=0;i<n;++i) ++cnt[x[i]=s[i]];	for(int i=1;i<m;++i) cnt[i]+=cnt[i-1];	for(int i=n-1;i>=0;--i) SA[--cnt[x[i]]]=i;	for(int k=1;k<=n;k<<=1){		int p=0;		for(int i=n-k;i<n;++i) y[p++]=i;		for(int i=0;i<n;++i) if(SA[i]>=k) y[p++]=SA[i]-k;		for(int i=0;i<m;++i) cnt[i]=0;		for(int i=0;i<n;++i) ++cnt[x[y[i]]];		for(int i=1;i<m;++i) cnt[i]+=cnt[i-1];		for(int i=n-1;i>=0;--i) SA[--cnt[x[y[i]]]]=y[i];		p=1;		swap(x,y);		x[SA[0]]=0;		for(int i=1;i<n;++i){			if(same(y,i,i-1,k)) x[SA[i]]=p-1;			else x[SA[i]]=p++;		}		if(p>=n) break;		m=p;	}}void getHeight(){	for(int i=0;i<n;++i)		rk[SA[i]]=i;	height[0]=0;	for(int i=1;i<n;++i){		int k=0;		while(s[SA[i]+k]==s[SA[i-1]+k]) ++k;		height[i]=k;	}}void getAns(){	for(int i=0;i<n;++i) ans[i][i]=n-i;	for(int i=0;i<n;++i){		int minn=n;		for(int j=i+1;j<n;++j){			minn=min(minn,height[j]);			ans[SA[i]][SA[j]]=ans[SA[j]][SA[i]]=minn;		}	}}int main(){	int q,a,b;	while(~scanf("%d",&n))	{		scanf("%s",s);		buildSA();		getHeight();		getAns();		in(q);		while(q--)		{			in(a);			in(b);			out(ans[a][b]);			puts("");		}	}	return 0;}