#include <bits/stdc++.h>
using namespace std;
const int HASH = 10007;
const int maxn = 2010;
typedef unsigned long long ull;
struct HASHMAP{
    int head[HASH], next[maxn], size;
    ull state[maxn];
    int f[maxn];
    void init(){
        size = 0;
        memset(head, -1, sizeof(head));
    }
    int insert(ull val, int _id){
        int h = val%HASH;
        for(int i=head[h]; ~i; i=next[i]){
            if(val == state[i]){
                int temp = f[i];
                f[i] = _id;
                return temp;
            }
        }
        f[size] = _id;
        state[size] = val;
        next[size] = head[h];
        head[h] = size++;
        return 0;
    }
}H;
const int SEED = 1331;
ull p[maxn];
ull s[maxn];
char str[maxn];
int ans[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    p[0] = 1;
    for(int i=1; i<maxn; i++){
        p[i] = p[i-1]*SEED;
    }
    int t;
    cin>>t;
    while(t--){
        cin>>str;
        int n = strlen(str);
        s[0] = 0;
        for(int i=1; i<=n; i++){
            s[i] = s[i-1]*SEED+str[i-1];
        }
        memset(ans, 0, sizeof(ans));
        for(int l=1; l<=n; l++){
            H.init();
            for(int i=1; i+l-1<=n; i++){
                int temp = H.insert(s[i+l-1]-s[i-1]*p[l], i);
                //cout<<"gg"<<endl;
                ans[i][i+l-1]++;//区间的hash值
                ans[temp][i+l-1]--;
            }
        }
        for(int i=n; i>=0; i--){
            for(int j=i; j<=n; j++){
                ans[i][j] += ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
            }
        }
        int q, u, v;
        cin>>q;
        while(q--){
            cin>>u>>v;
            cout<<ans[u][v]<<endl;
        }
    }
    return 0;
}