#include <cstdio>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define getmid(l,r) ((l) + ((r) - (l)) / 2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define MP(a,b) make_pair(a,b)
#define PB push_back

typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int INF = (1 << 30) - 1;
const int MOD = 1000000007;

struct Hash{
  int B,mod,len,Has[1005],Base[1005];
  void init(char *s,int _len,int _B,int _mod){
    B=_B; mod=_mod; len=_len;
    Base[0]=1; Has[0]=0; 
    for (int i=1;i<=len;i++){
      Base[i]=1ll*Base[i-1]*B%mod;
      Has[i]=(1ll*Has[i-1]*B+s[i-1]-'a'+1)%mod;
    }
    return;
  }
  int gethash(int l,int r){
    return ((Has[r]-1ll*Has[l-1]*Base[r-l+1])%mod+1ll*mod)%mod;
  }
};

Hash H1;

int T,Q,len;
char s[1010];
int g[1010][1010];
int num[1010];
vector<int> q[1010];
int X[100010];
int ans[100010];
int dp[1010][1010];
int C[1010];
map<int,int> mp;

inline void Update(int x,int d){
    while(x <= len){
        C[x] += d;
        x += x & (-x);
    }
}

inline int Getsum(int x){
    int res = 0;
    while(x){
        res += C[x];
        x -= x & (-x);
    }
    return res;
}

void Pre_cal(){
    for(int j = 1; j <= len; ++j){
        for(int i = 1; i <= j; ++i){
            if(i == j || ((i + 1 == j) && s[i - 1] == s[j - 1]) || 
                ((i + 1 < j) && dp[i + 1][j - 1] && s[i - 1] == s[j - 1])){
                ++num[j];
                g[j][num[j]] = i;
                dp[i][j] = 1;
            }
        }
    }
}

inline void Init(){
    for(int i = 1; i <= len; ++i) q[i].clear();
    memset(dp,0,sizeof(dp));
    memset(num,0,sizeof(num));
    memset(C,0,sizeof(C));
    mp.clear();
}

inline int Read(){
      int x = 0; char ch = getchar();
      while(ch < '0' || ch > '9') ch = getchar();
      while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
      return x;
}

int main(){
    T = Read();
    while(T--){
        scanf("%s",s);
        len = strlen(s);
        Init();
        H1.init(s,len,171,MOD);
        Pre_cal();
        Q = Read();
        for(int i = 1; i <= Q; ++i){
            int x = Read(),y = Read();
            X[i] = x;
            q[y].PB(i);
        }
        for(int i = 1; i <= len; ++i){
            for(int j = 1; j <= num[i]; ++j){
                int h1 = H1.gethash(g[i][j],i);
                int p = mp[h1];
                if(p){
                    Update(p,-1);
                }
                mp[h1] = g[i][j];
                Update(g[i][j],1);
            }
            for(int j = 0; j < q[i].size(); ++j){
                ans[q[i][j]] = Getsum(i) - Getsum(X[q[i][j]] - 1);
            }
        }
        for(int i = 1; i <= Q; ++i){
            printf("%d\n",ans[i]);    
        }
    }
    return 0;
}