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

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
// #define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

// MOD 2^64
typedef unsigned long long ULL;
struct RollingHash {
    static const ULL BASE = 2e9 + 11; // 3e9+19, 4e9+7 
    static const int MAX_LEN = 1000000;
    static const vector<ULL>powB;
    static const vector<ULL>buildB();
    vector<char> S;
    vector<ULL> H; // H[i] := hash(S[0 .. i])
    RollingHash(const string &str) {
    init(str);
    }
    void init(const string &str) {
    S.clear(); H.assign(1, 0ULL);
    for (int i=0; i<(int)str.size(); i++) {
        S.push_back(str[i]);
        H.push_back(H.back() * BASE + str[i]);
    }
    }
    inline ULL get(int l, int r) { // hash(S[l .. r-1])
    return H[r] - H[l] * powB[r-l];
    }
    void push(char c) {
    S.push_back(c);
    H.push_back(H.back() * BASE + c);
    }
    void pop() {
    S.pop_back();
    H.pop_back();
    }
};
const vector<ULL>RollingHash::buildB() {
    vector<ULL>h(MAX_LEN);
    h[0] = 1;
    for (int i=1; i<MAX_LEN; i++) h[i] = h[i-1]*BASE;
    return h;
}
const vector<ULL>RollingHash::powB = RollingHash::buildB();

template<class T>
struct Fenwick : vector<T> {
    typedef vector<T> S;
    int N;
    Fenwick(int N_=0): S(N_), N(N_) {}
    void add(int i, T x) {
    for (; i<N; i|=i+1) S::operator[](i) += x;
    }
    inline T sum(int r) {
    T s = 0;
    for (; r; r&=r-1) s += S::operator[](r-1);
    return s;
    }
    T sum(int l, int r) {
    return sum(r) - sum(l);
    }
};

struct Manacher {
    vector<int>rad;
    Manacher(){}
    Manacher(const string &t) {
    int n = t.size(), i, j, k;
    rad.assign(2*n, 0);
//    rad = vector<int>(2*n);
    for (i=0, j=0; i<2*n; i+=k, j=max(j-k, 0)) {
        while (i-j >= 0 && i+j+1 < 2*n && t[(i-j)/2] == t[(i+j+1)/2]) j++;
        rad[i] = j;
        for (k=1; i-k >= 0 && rad[i]-k >= 0 && rad[i-k] != rad[i]-k; k++)
        rad[i+k] = min(rad[i-k], rad[i]-k);
    }
    }
    inline bool ok(int l, int r) { // [l, r)
        return r-l <= rad[l+r-1];
    }
    pair<int, int> span(int mid, bool ev/*=even length str*/) { 
    if (ev) { // [mid-2, mid-1, mid, mid+1]
        return make_pair(mid - rad[mid*2+1]/2, mid + rad[mid*2+1]/2);
    } else { // [mid-1, mid, mid+1]
        return make_pair(mid - rad[mid*2]/2, mid + rad[mid*2]/2 + 1);
    }
    }
};



char S[10111];
int N, Q;
struct Query {
    int l, r, i;
    bool operator<(const Query &y) const {
    return r < y.r;
    }
} D[1000111];
int ans[1000111];

map<ULL, int> mp[10111];

void TEST() {
    N = 1000;
    REP (i, N) S[i] = 'a' + rand() % 1;
    Q = 0;
    while (true) {
    if (Q >= 1000000) break;
    D[Q].l = rand() % N;
    D[Q].r = rand() % N;
    if (D[Q].l > D[Q].r) swap(D[Q].l, D[Q].r);
    D[Q].r++;
    D[Q].i = Q;
    Q++;
    }
}

void MAIN() {
    scanf("%s%d", S, &Q);
    REP (i, Q) {
    scanf("%d%d", &D[i].l, &D[i].r);
    D[i].l--;
    D[i].i = i;
    }
//    TEST();
    sort(D, D+Q);

    N = strlen(S);
    Manacher M(S);
    RollingHash R(S);
    REP (i, N+1) mp[i].clear();
    Fenwick<int> F(N+2);

    for (int i=0, j=0; i<Q; i++) {
    while (j < D[i].r) {
        REP (k, j+1) if (M.ok(k, j+1)) {
        int l = j+1 - k;
        ULL h = R.get(k, j+1);
        map<ULL,int>::iterator it = mp[l].find(h);
        if (it != mp[l].end()) {
            F.add(it->second, -1);
            F.add(it->second = k, 1);
        } else {
            mp[l].insert(make_pair(h, k));
            F.add(k, 1);
        }
        }
        j++;

//        REP (k, N) eprintf("%d ", F.sum(k, k+1));
//        eprintf("\n");
    }

    ans[D[i].i] = F.sum(D[i].l, D[i].r);
    }

    REP (i, Q) printf("%d\n", ans[i]);
}

int main() {
    int T;
    scanf("%d", &T);
    REP (i, T) MAIN();
    return 0;
}