#include <cstdio>
#include <cstring>
#include <algorithm>
#include <memory.h>
using namespace std;

#define N 3010
#define M 100100

char s[N];
int n, m;
int f[N][N], a[N];
int nx[26][N];
int g[N], vis[N], gg[N];

struct query {
    int l, r, id;
    query(int l = 0, int r = 0, int id = 0) : l(l), r(r), id(id) {}
    bool operator <(const query &a) const { return r < a.r; }
}q[M];
int ans[M];

void input(int &x) {
    x = 0;
    char c = getchar();
    while('0' > c || c > '9') c = getchar();
    while('0' <= c && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
}

void inpu(char *s) {
    int cnt = 0;
    char c = getchar();
    while('a' > c || c > 'z') c = getchar();
    while('a' <= c && c <= 'z') s[cnt ++] = c, c = getchar();
    s[cnt] = 0;
}

int buf[100];

void print(int x) {
    if(!x) {
        puts("0"); return;
    }
    int c = 0;
    while(x) {
        buf[c ++] = x % 10; x /= 10;
    }
    while(c --) putchar('0' + buf[c]);
    puts("");
}

void init() {
    for(int i = 0; i < 26; i ++) vis[i] = 0;
    for(int i = 1; i <= n; i ++) {
        if(!vis[a[i]]) {
            vis[a[i]] = ++ m;
            f[i][i] = m;
        } else f[i][i] = vis[a[i]];
    }
    for(int i = 0; i < 26; i ++) vis[i] = 0;
    for(int i = 1; i < n; i ++) if(a[i] == a[i+1]) {
        if(!vis[a[i]]) {
            vis[a[i]] = ++ m;
            f[i][i+1] = m;
        } else f[i][i+1] = vis[a[i]];
    } else f[i][i + 1] = 0;
    for(int d = 2; d < n; d ++) {
        for(int i = 1; i + d <= n; i ++) {
            int j = i + d;
            int k = f[i + 1][j - 1];
            if(!k || a[i] != a[j]) {
                f[i][j] = 0;
                continue;
            }
            if(nx[a[i]][k]) {
                f[i][j] = nx[a[i]][k];
            } else {
                f[i][j] = ++ m;
                nx[a[i]][k] = m;
            }
        }
    }
}

void add(int x) {
    while(x) {
        g[x] ++;
        x -= x&-x;
    }
}

void minu(int x){
    while(x) {
        g[x] --;
        x -= x&-x;
    }
}

int calc(int l) {
    int rt = 0;
    while(l <= n) {
        rt += g[l];
        l += l&-l;
    }
    return rt;
}

void update(int r) {
    for(int i = 1; i <= r; i ++) if(f[i][r]) {
        int k = f[i][r];
        minu(gg[k]);
        add(i); gg[k] = i;
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("3.in","r", stdin); freopen("3.out", "w", stdout);
    int T;
    for(input(T); T --; ) {
        inpu(s + 1);
        n = strlen(s + 1);
        for(int i = 1; i <= n; i ++) a[i] = s[i] - 'a';
        m = 0;
        memset(nx, 0, sizeof(nx));
        memset(g, 0, sizeof(g));
        memset(gg, 0, sizeof(gg));
        init();
        int Q;
        input(Q);
        for(int i = 0; i < Q; i ++) {
            input(q[i].l);
            input(q[i].r);
            q[i].id = i;
        }
        sort(q, q + Q);
        int cur = 1;
        for(int i = 0; i < Q; i ++) {
            while(cur <= q[i].r) {
                update(cur); cur ++;
            }
            ans[q[i].id] = calc(q[i].l);
        }
        for(int i = 0; i < Q; i ++) {
            print(ans[i]);
        }
    }
    return 0;
}