51nod除了在做OJ之外，还开展了很多副业。婚姻介绍所就是其中之一。

对于一个客户，我们可以使用一个字符串来描述该客户的特质。

假设现在我们有两个客户A和B。

A的特质字符串为：abcdefg
B的特质字符串为：abcxyz

则A和B的匹配度f(A, B)为A和B的最长公共前缀的长度，即len(‘abc’) = 3

由于最近51nod经费紧张，所以夹克大老爷设计了一种压缩算法以节约内存。

所有用户的特质字符串都被存储在了一个长为n的字符串S中。(n <= 1000)用户的特质使用一个整数p表示，表示该用户的特质字符串为S[p…n - 1]。

现给定字符串S，与q次查询<ai, bi>（ai, bi分别为合法的用户特质整数）。请输出q次查询分别对应的客户匹配度。

现给定字符串长度n，与字符串S。接下来是整数q，代表接下来有q次查询。
下面q行有两个整数ai, bi。代表查询特质为ai与bi的用户的匹配度。

1 <= n <= 1000
1 <= q <= 10^6

输入数据全部合法。

每一行输出一个用户匹配度整数。

题意：求给定x位置的后缀与y位置的后缀的最长公共前缀
思路：后缀x和后缀y的最长公共前缀
min(height[rak[x]+1], height[rak[x] + 2]…height[rak[y]])
使用RMQ预处理出height数组，然后O（1）时间复杂度查询最长公共前缀

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char s[maxn];
struct node {
	int x, y, id;
}a[maxn], b[maxn];
int n, m, p;
int sa[maxn], rak[maxn], tx[maxn];
int lg[maxn];
void rsort() {
	for (int i = 1; i <= m; i++) {
		tx[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		tx[a[i].y]++;
	}
	for (int i = 1; i <= m; i++) {
		tx[i] += tx[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		b[tx[a[i].y]--] = a[i];
	}
	for (int i = 1; i <= m; i++) {
		tx[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		tx[b[i].x]++;
	}
	for (int i = 1; i <= m; i++) {
		tx[i] += tx[i - 1];
	}
	for (int i = n; i >= 1; i--) {
		a[tx[b[i].x]--] = b[i];
	}
}

void solve() {
	rsort();
	p = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) {
			rak[a[i].id] = p;
		} else {
			rak[a[i].id] = ++p;
		}
	}
	for (int i = 1; i <= n; i++) {
		a[i].x = rak[i];
		a[i].id = sa[rak[i]] = i;
		a[i].y = 0;
	}
	m = p;
}
void ssort() {
	m = 127;
	for (int i = 1; i <= n; i++) {
		a[i].x = a[i].y = s[i];
		a[i].id = i;
	}
	solve();
	for (int j = 1; j <= n; j <<= 1) {
		for (int i = 1; i + j <= n; i++) {
			a[i].y = a[i + j].x;
		}
		solve();
		if (p == n) {
			break;
		}
	}
}

int height[maxn];
inline void get_Height(){//求Height数组
    int k=0;
    for(int i=1;i<=n;++i){
        if(k)k--;
        int j=sa[rak[i]-1];
        while(s[i+k]==s[j+k])++k;
        height[rak[i]]=k;
    }
}

int dp[maxn][20];

void RMQ() {
	lg[0] = -1;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = height[i];
		lg[i] = lg[i >> 1] + 1;
	}
	for (int j = 1; j <= lg[n]; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
		}
	}
}


inline int read(){
    int k=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
    return k*f;
}
int main() {
	n = read();
	scanf("%s", s + 1);
	n = strlen(s + 1);
    ssort();
    get_Height();
    m = read();
    int x, y, l, r;
    RMQ();
    while (m--) {
    	x = read(); y = read();
    	x++; y++;
    	if (x == y) {
    		printf("%d\n", n - x + 1); 
		} else {
			l = rak[x];
			r = rak[y];
			if (l > r) {
				swap(l, r);
			}
			l++;
			int k = lg[r - l + 1];
			printf("%d\n", min(dp[l][k], dp[r - (1 << k) + 1][k]));
		}
	}
    return 0;
}