#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void strcpyx(char target,const char dest,int i,int j)
{
int x=0,c=0;
for(x=i;x<=j;x++)
{
target[c++]=dest[x];
}
target[c]='\0';
}
int main()
{
int t=0,i=0,m=0,j=0,k=0,sum=0,c=0,fin=0,count=0;
int *l=NULL;int *u=NULL;int *ans=NULL;
char** sub=NULL;char **orig=NULL;
char* temp=NULL;
char str[50000]="";
scanf("%d",&t);
while(t>0)
{
scanf("%s",&str);
scanf("%d",&m);
ans=(int*)malloc(sizeof(int)*m);
l=(int*)malloc(sizeof(int)*m);
u=(int*)malloc(sizeof(int)*m);
count=0;
for(i=0;i<m;i++)
{
scanf("%d",&l[i]);
scanf("%d",&u[i]);
}
for(i=0;i<m;i++)
{
sum=0;
for(j=l[i]-1;j<u[i];j++)
{
for(k=j;k<strlen(str);k++)
{
sum=sum+1;
}
}
c=0;
sub=(char**)malloc(sizeof(char*)*sum);
for(j=l[i]-1;j<u[i];j++)
{
for(k=j;k<strlen(str);k++)
{
sub[c]=(char*)malloc(sizeof(char)*(k-j+2));
strcpyx(sub[c],str,j,k);
//printf("%d %s\n",strlen(sub[c]),sub[c]);
c++;
}
//sub[i]=(char*)malloc(sizeof(char)*)
}
for(k=0;k<sum;k++)
{
for(j=0;j<sum-1-k;j++)
{
if(strlen(sub[j])>strlen(sub[j+1]))
{
temp=sub[j+1];
sub[j+1]=sub[j];
sub[j]=temp;
}
if(strlen(sub[j])==strlen(sub[j+1]))
{
if(strcmp(sub[j],sub[j+1])>0)
{
temp=sub[j+1];
sub[j+1]=sub[j];
sub[j]=temp;
}
}
}
}
fin=0;
//printf("sum=%d c=%d\n",sum,c );
//for(j=0;j<c;j++)
//printf("%d %s\n",strlen(sub[j]),sub[j]);
for(j=1;j<sum;j++)
{
if(strlen(sub[j])==strlen(sub[j-1]))
{
if(strcmp(sub[j],sub[j-1])!=0)
{
if(j==1)
fin+=2;
else
fin++;
}
else
{
if(j==1)
fin++;
}
}
else
if(j==1)
fin+=2;
else
fin++;
}
if(sum==1)
fin=1;
ans[count++]=fin;
for(j=0;j<sum;j++)
free(sub[j]);
free (sub);
}
for(i=0;i<count;i++)
printf("%d\n",ans[i]);
free(ans);
free(l);
free(u);
t--;
}
return 0;
}