InputFirst line contains T denoting the number of testcases.

T testcases follow. For each testcase:

First line contains a string S. We ensure that it is contains only with lower case letters.

Second line contains a interger Q, denoting the number of queries.

Then Q lines follow, In each line there are two intergers l,r, denoting the substring which is queried.

1≤T≤10, 1≤length≤1000, 1≤Q≤100000, 1≤l≤r≤length
OutputFor each testcase, output the answer in Q lines.Sample Input

1

abba

2

1 2

1 3

Sample Output

2

3

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

char c[maxn]; int bb[maxn];

int N,Q,fcy[maxn][maxn];

struct PT

{

    struct node{

        int fail,len,son[];

    }t[maxn];

    int tot,last;

    void init()

    {

        memset(t,,sizeof(t));

        t[].fail=t[].fail=;

        t[].len=-;

        last=; tot=; bb[]=-; bb[]=-;

    }

    void add(int s,int n)

    {

        int p=last; bb[n]=s;

        while(bb[n-t[p].len-]!=bb[n]) p=t[p].fail;

        if(!t[p].son[s])

        {

            int v=++tot,k=t[p].fail;

            t[v].len=t[p].len+;

            while(bb[n-t[k].len-]!=bb[n]) k=t[k].fail;

            t[v].fail=t[k].son[s];

            t[p].son[s]=v;

        }

        last=t[p].son[s];

    }

}T;

void solve()

{

    rep(i,,N){

        T.init();

        rep(j,i,N) {

            T.add(c[j]-'a',j-i+);

            fcy[i][j]=T.tot-;

        }

    }

    scanf("%d",&Q);

    rep(i,,Q){

       int L,R; scanf("%d%d",&L,&R);

       printf("%d\n",fcy[L][R]);

    }

}

int main()

{

    int T;scanf("%d",&T);

    while(T--){

        memset(c,,sizeof(c));

        scanf("%s",c+);

        N=strlen(c+);

        solve();

    }

    return ;

}