//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=998244853,base=301;
string s;
ll h1[500500],h2[500500],pw[500500];
ll get(int l,int r)
{
	return (h1[r]-h1[l-1]*pw[r-l+1]%mod+mod)%mod;
}
ll getr(int l,int r)
{
	return (h2[l]-h2[r+1]*pw[r-l+1]%mod+mod)%mod;
}
int L[500500],R[500500];
vector<pii> vq1[500500],vq2[500500];
vector<pii> vec1[500500],vec2[500500];
int ql[500500],qr[500500],len[500500];
int d[1000100];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n>>s;
	s=' '+s;
	pw[0]=1;
	for(int i=1;i<500500;i++)
		pw[i]=pw[i-1]*base%mod;
	for(int i=1;i<=n;i++)
		h1[i]=(h1[i-1]*base+s[i])%mod;
	for(int i=n;i>=1;i--)
		h2[i]=(h2[i+1]*base+s[i])%mod;
	for(int i=1;i<=n;i++)
	{
		int l=1,r=min(i,n-i+1);
		while(l<r)
		{
			int mid=(l+r+1)/2;
			if(get(i,i+mid-1)==getr(i-mid+1,i))
				l=mid;
			else
				r=mid-1;
		}
		d[i+i]=l;
		vec1[i-l+1].pb(i+i,1);
		vec1[i+1].pb(i+i,0);
		vec2[i+l-1].pb(i+i,1);
		vec2[i-1].pb(i+i,0);
	}
	for(int i=1;i<n;i++)
	{
		if(s[i]!=s[i+1]) continue;
		int l=1,r=min(i,n-i);
		while(l<r)
		{
			int mid=(l+r+1)/2;
			if(get(i+1,i+mid)==getr(i-mid+1,i))
				l=mid;
			else
				r=mid-1;
		}
		d[i+i+1]=l;
		vec1[i-l+1].pb(i+i+1,1);
		vec1[i+1].pb(i+i+1,0);
		vec2[i+l].pb(i+i+1,1);
		vec2[i].pb(i+i+1,0);
	}
	int q;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>ql[i]>>qr[i];
		int l=0,r=(qr[i]-ql[i]+1)/2;
		while(l<r)
		{
			int mid=(l+r+1)/2;
			if(get(ql[i],ql[i]+mid-1)==getr(qr[i]-mid+1,qr[i]))
				l=mid;
			else
				r=mid-1;
		}
		len[i]=l;
		vq1[ql[i]+l].pb(ql[i]+qr[i],i);
		vq2[qr[i]-l].pb(ql[i]+qr[i],i);
	}
	multiset<int> st;
	for(int i=1;i<=n;i++)
	{
		for(auto pr:vec1[i])
			if(pr.second)
				st.insert(pr.first);
			else
				st.erase(st.lower_bound(pr.first));
		for(auto pr:vq1[i])
		{
			auto it=st.upper_bound(pr.first);
			if(it!=st.begin())
			{
				it--;
				L[pr.second]=(*it)-i-i+1;
			}
		}
	}
	st.clear();
	for(int i=n;i>=1;i--)
	{
		for(auto pr:vec2[i])
			if(pr.second)
				st.insert(pr.first);
			else
				st.erase(st.lower_bound(pr.first));
		for(auto pr:vq2[i])
		{
			auto it=st.lower_bound(pr.first);
			if(it!=st.end())
				R[pr.second]=i-((*it)-i)+1;
		}
	}
	for(int i=1;i<=q;i++)
	{
		int ans1;
		cout<<(ans1=((qr[i]-ql[i]+1)-min(qr[i]-ql[i]+1,max(L[i],R[i])+len[i]*2)))<<" ";
		if(!ans1)
			cout<<"0\n";
		else
		{
			int ans2=0;
			if(L[i]>=R[i])
			{
				int lp1=ql[i]+len[i];
				int lp2=lp1+L[i]-1;
				int len1=(L[i]+1)/2;
				int len2=len1+len[i];
				len2=min(len2,d[lp1+lp2]);
				ans2+=max(0,len2-len1+1);
			}
			if(R[i]>=L[i])
			{
				int rp1=qr[i]-len[i];
				int rp2=rp1-R[i]+1;
				int len1=(R[i]+1)/2;
				int len2=len1+len[i];
				len2=min(len2,d[rp1+rp2]);
				ans2+=max(0,len2-len1+1);
			}
			cout<<ans2<<'\n';
		}
	}
	return 0;
}