#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N=1005;
const int MOD=12135131;
int T,n,ans,f[N][N],g[N][N],F[N],q[N][N],m,l,r;
bool o[MOD];
char s[N];

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

int main()
{
    cin>>T;
    while (T--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        for (int i=1;i<=n;i++) 
            for (int j=i;j<=n;j++) f[i][j]=(f[i][j-1]*27+s[j]-'a'+1)%MOD;
        for (int i=1;i<=n;i++) 
            for (int j=i;j;j--)
                g[i][j]=(g[i][j+1]*27+s[j]-'a'+1)%MOD;
        for (int i=n;i;i--)
        {
            for (int j=i;j<=n;j++) 
            {
                if (f[i][j]==g[j][i]) F[j]=f[i][j];
                if (!o[F[j]])
                {
                    o[F[j]]=1; q[i][j]=q[i][j-1]+1;
                }  else q[i][j]=q[i][j-1];
            }
            for (int j=i;j<=n;j++) o[F[j]]=0;
        }
        cin>>m;
        for (int i=1;i<=m;i++) 
        {
            l=read(); r=read();
            printf("%d\n",q[l][r]);
        }
    }
}