#include<stdio.h>
#include<string.h>


using namespace std;

#define SEED 13331
#define MAXN  2007
#define HASH 10007

int head[HASH];
int cnt;
struct node
{
    int id,next;
    unsigned long long v;

}edge[MAXN];

char str[MAXN];
unsigned long long s[MAXN],p[MAXN];
int ans[MAXN][MAXN];

int ins(unsigned long long val,int id)
{
    int b=0;
    int h=val%HASH;
    for(int i=head[h];i!=-1;i=edge[i].next)
    {
        if(val==edge[i].v)
        {
            int a=edge[i].id;
            edge[i].id=id;
            return a;
        }

    }
    edge[cnt].id=id;
    edge[cnt].v=val;
    edge[cnt].next=head[h];
    head[h]=cnt++;
    return 0;
}

int main()
{
    int t;
    scanf("%d",&t);
    p[0]=1;
    for(int i=1;i<MAXN;i++)
        p[i]=p[i-1]*SEED;

    while(t--)
    {
        scanf("%s",str);
        s[0]=0;
        int len=strlen(str);
        for(int i=1;i<=len;i++)
            s[i]=s[i-1]*SEED+str[i-1];
        memset(ans,0,sizeof(ans));
       // printf("111\n");
        for(int l=1;l<=len;l++)
        {
            cnt=0;
            memset(head,-1,sizeof(head));
            for(int i=1;i+l-1<=len;i++)
            {
                int pos=ins(s[i+l-1]-s[i-1]*p[l],i);
                ans[i][i+l-1]++;
                ans[pos][i+l-1]--;
            }
        }

        for(int i=len;i>=1;i--)
            for(int j=i;j<=len;j++)
                ans[i][j]+=ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
        int m;
        scanf("%d",&m);
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            printf("%d\n",ans[a][b]);
        }
    }

    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include<set>
#include<deque>
#include<queue>
#include<stack>

using namespace std;

#define inf 1000000007
#define MAXN 50010
#define ll long long

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        ll a,b;
        if(n%2==1)
        {
            a=n/2;
            b=a+1;
        }
        else
        {
            int en=n/2;
            for(int i=en;i>=1;i--)
            {
                b=i;
                a=n-i;
                if(gcd(a,b)==1)
                {
                    break;
                }
            }
        }
        printf("%lld\n",a*b);

    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include<set>
#include<deque>
#include<queue>
#include<stack>

using namespace std;

#define inf 1000000007
#define MAXN 50010
#define ll long long

char s[30];
char s1[30];
bool jud[70000];
int dp[70000],len;

    bool check(int x){
        if(x == 0)return true;
        int i=0,j=len-1;
        while(i<j){
            while(!(x&(1<<i)))++i;
            while(!(x&(1<<j)))--j;
            if(s[i] != s[j])return false;
            ++i,--j;
        }
        return true;
    }


int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        len=strlen(s);
        int en=1<<len;
        int en1=len/2;

        for(int i=0;i<en;i++)
        {
            jud[i]=check(i);
        }
        for(int i=0;i<en;i++)
            dp[i]=inf;
        dp[en-1]=0;
        for(int i=en-1;i>=0;--i)
        {
            for(int j=i;j>=1;j=((j-1)&i))
            {
                if(!jud[i^j])
                    continue;
                if(dp[j]>dp[i]+1)
                    dp[j]=dp[i]+1;
            }
            if(jud[i]&&dp[0]>dp[i]+1)
                dp[0]=dp[i]+1;
        }
        printf("%d\n",dp[0]);

    }
    return 0;
}

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>

using namespace std;

#define MAXN  50010
int z[MAXN];
struct qu
{
    int l,r,id;
}q[MAXN];

struct node
{
    int l,r,w;
}tree[MAXN<<2];

bool cmp(qu a, qu b)
{
    return a.r<b.r;
}
int pre[MAXN];
int ans[MAXN];

void Build(int l,int r,int a)
{
    tree[a].l=l;
    tree[a].r=r;
    tree[a].w=0;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    Build(l,mid,a<<1);
    Build(mid+1,r,a<<1|1);
}

void update(int l,int r,int a1,int b1,int a)
{
    if(l==r)
    {
        tree[a].w=max(tree[a].w,b1);
        return ;
    }
    int mid=(l+r)>>1;
    if(a1<=mid)
        update(l,mid,a1,b1,a<<1);
    else
        update(mid+1,r,a1,b1,a<<1|1);
    tree[a].w=max(tree[a<<1].w,tree[a<<1|1].w);
}
int Ques(int l,int r,int a1,int b1,int a)
{
    if(a1<=l&&r<=b1)
        return tree[a].w;
    int ans=0;
    int mid=(l+r)>>1;
    if(a1<=mid)
        ans=max(ans,Ques(l,mid,a1,b1,a<<1));
    if(b1>mid)
        ans=max(ans,Ques(mid+1,r,a1,b1,a<<1|1));
    return ans;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&z[i]);
        int m;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q+1,q+m+1,cmp);
        memset(pre,-1,sizeof(pre));
        Build(1,n,1);
        int cnt=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j*j<=z[i];j++)
            {
                if(z[i]%j==0)
                {
                    if(z[i]%j==0&&pre[j]!=-1)
                        update(1,n,pre[j],j,1);
                    int b=z[i]/j;
                    if(j!=b&&z[i]%b==0&&pre[b]!=-1)
                        update(1,n,pre[b],b,1);
                    pre[j]=pre[b]=i;
                }
            }
            while(cnt<=m&&q[cnt].r==i)
            {
                ans[q[cnt].id]=Ques(1,n,q[cnt].l,q[cnt].r,1);
                cnt++;
            }
        }
        for(int i=1;i<=m;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}