#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 10010

using namespace std;

int next[maxn][26],pre[maxn],step[maxn];

int f[2002][2002];

char s[maxn];

int Q,N,last,T,l,r;

int p,q,np,nq;

int add()

{

    N++;

    for (int i=0; i<26; i++) next[N][i]=0;

    pre[N]=step[N]=0;

    return N;

}

int insert(int x)

{

    p=last,np=add(),step[np]=step[last]+1,last=np;

    while (p!=-1 && next[p][x]==0) next[p][x]=np,p=pre[p];

    if (p==-1) return step[np];

    q=next[p][x];

    if (step[q]==step[p]+1) { pre[np]=q; return step[np]-step[pre[np]]; }

    nq=add(),step[nq]=step[p]+1,pre[nq]=pre[q];

    for (int i=0; i<26; i++) next[nq][i]=next[q][i];

    pre[np]=pre[q]=nq;

    while (p!=-1 && next[p][x]==q) next[p][x]=nq,p=pre[p];

    return step[np]-step[pre[np]];

}

int main()

{

    scanf("%d",&T);

    while (T--)

    {

        scanf("%s",s+1);

        for (int i=1; s[i]; i++)

        {

            N=-1;N=add();last=0;pre[0]=-1;

            for (int j=i; s[j]; j++) f[i][j]=insert(s[j]-'a');

        }

        for (int i=1; s[i]; i++)

            for (int j=i+1; s[j]; j++) f[i][j]+=f[i][j-1];

        scanf("%d",&Q);

        while (Q--)

        {

            scanf("%d%d",&l,&r);

            printf("%d\n",f[l][r]);

        }

    }

    return 0;

}