#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define db double
#define ve vector<int>
#define pa pair<int,int>
#define fr first
#define sd second
#define pb push_back
#define mp make_pair
#define MEM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
#define N 500010
int n; string s;
int m;
const int mod = 998244353, seed = 131;
int H[N], h[N], ih[N];
int ck(int l1, int r1, int l2, int r2)
{
	if (l1 > l2)swap(l1, l2), swap(r1, r2);
	return (1LL * (h[r1] + mod - h[l1 - 1]) * H[l2 - l1] % mod) == ((h[r2] + mod - h[l2 - 1]) % mod);
}
int ick(int l1, int r1, int l2, int r2)
{
	if (l1 <= n - r2 + 1)return (1LL * (h[r1] + mod - h[l1 - 1]) * H[(n - r2 + 1) - l1] % mod) == ((ih[l2] + mod - ih[r2 + 1]) % mod);
	else return ((h[r1] + mod - h[l1 - 1]) % mod) == ((1LL * (ih[l2] + mod - ih[r2 + 1]) * H[l1 - (n - r2 + 1)]) % mod);
}
int lcs(int x, int y)
{
	int l = 1, r = min(x, y), ans = 0;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (ck(x - mid + 1, x, y - mid + 1, y))ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}
int lcp(int x, int y)
{
	int l = 1, r = min(n - x + 1, n - y + 1), ans = 0;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (ck(x, x + mid - 1, y, y + mid - 1))ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}
struct PAM
{
	string s;
	int fa[N], fail[N], ch[N][26];
	int tot, lst, id[N], len[N];
	vector<int>e[N];
	int rt[N];
	int ls[N << 5], rs[N << 5], sz[N << 5];
	int cnt;
	void add(int pos)
	{
		int p = lst, np; int x = s[pos] - 'a';
		while (s[pos - len[p] - 1] != s[pos])p = fail[p];
		if (!ch[p][x])
		{
			np = ++ tot; int t = fail[p];
			while (s[pos - len[t] - 1] != s[pos])t = fail[t];
			fail[np] = ch[t][x]; ch[p][x] = np; len[np] = len[p] + 2;
		}
		else np = ch[p][x];
		lst = np, id[pos] = np;
	}
	int qry(int l, int r, int x, int ql, int qr)
	{
		if (!sz[x])return -1;
		if (l == r)return l;
		int mid = (l + r) >> 1;
		if (l == ql && r == qr)
		{
			if (sz[rs[x]])return qry(mid + 1, r, rs[x], mid + 1, qr);
			else return qry(l, mid, ls[x], ql, mid);
		}
		if (qr <= mid)return qry(l, mid, ls[x], ql, qr);
		else if (ql > mid)return qry(mid + 1, r, rs[x], ql, qr);
		else
		{
			int t = qry(mid + 1, r, rs[x], mid + 1, qr);
			return (t == -1 ? qry(l, mid, ls[x], ql, mid) : t);
		}
	}
	int qry(int x, int k) {return qry(1, n, rt[id[x]], 1, k);}
	void add(int l, int r, int &x, int pos)
	{
		++ cnt; ls[cnt] = ls[x], rs[cnt] = rs[x], sz[cnt] = 1; x = cnt;
		if (l == r)return ;
		int mid = (l + r) >> 1;
		if (pos <= mid)add(l, mid, ls[x], pos);
		else add(mid + 1, r, rs[x], pos);
	}
	void dfs(int x, int fa)
	{
		if (fa != -1)rt[x] = rt[fa];
		add(1, n, rt[x], len[x]);
		for (int y : e[x])dfs(y, x);
	}
	void build()
	{
		tot = lst = 1; fail[1] = 0, fail[0] = 1; len[1] = -1;
		for (int i = 1; i <= n; i ++)add(i);
		for (int i = 2; i <= tot; i ++)e[fail[i]].push_back(i);
		e[1].push_back(0);
		dfs(1, -1);
	}
} A, B;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> s; string t = s; reverse(t.begin(), t.end());
	s = "0" + s, t = "0" + t;
	H[0] = 1; for (int i = 1; i <= n; i ++)H[i] = 1LL * H[i - 1] * seed % mod;
	for (int i = 1; i <= n; i ++)h[i] = (h[i - 1] + 1LL * H[i] * s[i]) % mod;
	for (int i = n; i >= 1; i --)ih[i] = (ih[i + 1] + 1LL * H[n - i + 1] * s[i]) % mod;
	A.s = s; B.s = t;
	A.build(), B.build();
	int m; cin >> m;
	while (m --)
	{
		int l, r;
		cin >> l >> r;
		int L = 1, R = (r - l + 1) / 2, v = 0;
		while (L <= R)
		{
			int mid = (L + R) >> 1;
			if (ick(l, l + mid - 1, r - mid + 1, r))v = mid, L = mid + 1;
			else R = mid - 1;
		}
		if (v == (r - l + 1) / 2) {cout << "0 0\n"; continue;}
		int l0 = l + v, r0 = r - v;
		int len1 = B.qry(n - l0 + 1, r0 - l0 + 1), len2 = A.qry(r0, r0 - l0 + 1);
		int ans = max(len1, len2), ans2 = 0;
		// cout << "???:" << len1 << ' ' << len2 << endl;
		// for (int i = l0; i <= r0; i ++)cout << s[i]; cout << endl;
		// for (int i = l; i <= r; i ++)cout << s[i]; cout << endl;
		cout << (r - l + 1) - 2 * v - ans << ' ';
		if (len1 == ans)
		{
			int len = min(lcp(l0 + len1, r0 + 1) + 1, l0 - l + 1);
			ans2 += len;
		}
		if (len2 == ans)
		{
			int len = min(lcs(r0 - len2, l0 - 1) + 1, r - r0 + 1);
			ans2 += len;
		}
		cout << ans2 << '\n';
	}
	return 0;
}