# 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;

}