#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int maxn = 100000 + 10;
const int MOD = 9973;
char s[maxn];
int h[maxn];
int main()
{
    int n, a, b;
    while(cin >> n) {
        getchar();
        gets(s);
        int len = strlen(s);
        h[0] = 1;
        for(int i = 1 ; i <= len ; i ++ ) {
                h[i] = h[i-1] * (s[i-1] - 28) ;
                h[i] %= MOD;
        }
        for(int i = 0 ; i < n ; i ++) {
            scanf("%d%d", &a, &b);
            if(a > b) swap(a, b);
            for(int i = 0 ; i < MOD ; i ++)
                if((h[a-1]*i - h[b])%MOD == 0 ) {
                    printf("%d\n", i);
                    break;
                }
        }

    }
    return 0;
}