#include<stdio.h>
#include<string.h>
inline void in(int &TEMP){int EPX;for(TEMP=getchar();TEMP<48||TEMP>57;TEMP=getchar());for(TEMP^=48,EPX=getchar();EPX<58&&EPX>47;EPX=getchar())TEMP=(TEMP<<3)+(TEMP<<1)+(EPX^48);}
struct PAM{
    int cnt,last;
    int son[1210][26],fa[1210],l[1210];
    char ch[1210];
    inline void clr(){
        memset(son,0,sizeof(son)),memset(fa,0,sizeof(fa));
        memset(ch,0,sizeof(ch));
        cnt=1,fa[0]=fa[1]=1,l[1]=-1;
    }
    inline void add(int c,int n){
        int p=last;ch[n]=c+'a';
        while(ch[n-l[p]-1]!=ch[n]) p=fa[p];
        if(!son[p][c]){
            int now=++cnt,k=fa[p];
            l[now]=l[p]+2;
            while(ch[n-l[k]-1]!=ch[n]) k=fa[k];
            fa[now]=son[k][c],son[p][c]=now;
        }
        last=son[p][c];
    }
}pam;
char s[1010];
int ans[1010][1010];
int main(){
    int T,len,Q,l,r;
    for(in(T);T--;){
        scanf("%s",s+1),len=strlen(s+1);
        for(int i=1;i<=len;++i){
            pam.clr();
            for(int j=i;j<=len;++j)
                pam.add(s[j]-'a',j),ans[i][j]=pam.cnt-1;
        }
        for(in(Q);Q--;printf("%d\n",ans[l][r]))
            in(l),in(r);
    }
}