#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
uint SA[200005],Rank[200005],H[200005],n;chr C[200005];
voi build()
{
for(uint i=0;i<n;i++)SA[i]=i;
std::sort(SA,SA+n,[&](uint a,uint b){return C[a]<C[b];});
for(uint i=0;i<n;i++)Rank[SA[i]]=i&&C[SA[i]]==C[SA[i-1]]?Rank[SA[i-1]]:i;
for(uint h=0;(1u<<h)<n;h++)
{
static uint Cnt[200005];
for(uint i=0;i<(1u<<h);i++)H[i]=i+n-(1u<<h);
for(uint i=0,j=1u<<h;i<n;i++)if(SA[i]>=(1u<<h))H[j++]=SA[i]-(1u<<h);
for(uint i=0;i<n;i++)Cnt[i]=0;
for(uint i=0;i<n;i++)Cnt[Rank[i]]++;
for(uint i=1;i<n;i++)Cnt[i]+=Cnt[i-1];
for(uint i=n-1;~i;i--)SA[--Cnt[Rank[H[i]]]]=H[i];
bol ok=true;
for(uint i=0;i<n;i++)H[SA[i]]=i&&Rank[SA[i-1]]==Rank[SA[i]]&&(SA[i-1]+(1u<<h)<n?Rank[SA[i-1]+(1u<<h)]:-1u)
==(SA[i]+(1u<<h)<n?Rank[SA[i]+(1u<<h)]:-1u)?(ok=false,H[SA[i-1]]):i;
for(uint i=0;i<n;i++)Rank[i]=H[i];
if(ok)break;
}
for(uint i=0,j=0;i<n;i++)
{
if(j)j--;
if(Rank[i])while(i+j<n&&SA[Rank[i]-1]+j<n&&C[i+j]==C[SA[Rank[i]-1]+j])j++;
H[Rank[i]]=j;
}
}
uint Fath[400005],Dep[400005],m;
std::vector<uint>Son[400005];
voi build2()
{
m=n+1,Fath[n]=-1;for(uint i=0;i<=n;i++)Dep[i]=n-i;
static uint S[200005],tp;S[0]=n,tp=1;
for(uint i=0;;i++)
{
uint lst=-1;
while(Dep[S[tp-1]]>H[i])
{
tp--;if(~lst)Fath[lst]=S[tp];
lst=S[tp];
}
if(Dep[S[tp-1]]<H[i])Dep[S[tp++]=m++]=H[i];
if(~lst)Fath[lst]=S[tp-1];
if(i<n)S[tp++]=SA[i];else break;
}
for(uint i=0;i<m;i++)if(i!=n)Son[Fath[i]].push_back(i);
}
namespace LCT
{
struct node
{
node*fath,*son[2];uint c;
inline bol ifroot(){return!fath||(this!=fath->son[0]&&this!=fath->son[1]);}
inline bol howson(){return this==fath->son[1];}
voi pushdown()
{
if(son[0])son[0]->c=c;
if(son[1])son[1]->c=c;
}
voi update()
{
if(!ifroot())fath->update();
pushdown();
}
voi rotate()
{
if(ifroot())return;
node*f=fath,*ff=fath->fath;bol sk=howson();
fath=ff;if(!f->ifroot())ff->son[f->howson()]=this;
if((f->son[sk]=son[!sk]))son[!sk]->fath=f;
(son[!sk]=f)->fath=this;
}
voi splay()
{
update();
while(!ifroot())
{
if(!fath->ifroot())(howson()==fath->howson()?fath:this)->rotate();
rotate();
}
}
}N[400005];
inline node*get(uint p){return N+p;}
inline uint get(node*p){return p-N;}
voi build(){for(uint i=0;i<m;i++)N[i]={~Fath[i]?get(Fath[i]):NULL,{NULL,NULL},-1u};}
voi color(node*p,uint c,std::vector<std::pair<uint,uint> >&D){
node*last=NULL;
while(p&&p->fath){
p->splay(),p->son[1]=last;
if(~p->c)D.push_back({p->c+Dep[get(p->fath)],p->c+Dep[get(p)]});
last=p,p=p->fath;
}
last->c=c;
}
}
std::vector<uint>Q[200005];
uint R[200005],q;
ullt B1[200005],B2[200005],Ans[200005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
scanf("%s",C);while(C[n])n++;
build(),build2(),LCT::build();
scanf("%u",&q);for(uint i=0,l;i<q;i++)scanf("%u%u",&l,R+i),Q[l-1].push_back(i);
for(uint i=n-1,p;~i;i--)
{
std::vector<std::pair<uint,uint> >D;
LCT::color(LCT::get(i),i,D);
for(auto s:D)
{
p=s.first+1;while(p<=n)B1[p]--,B2[p]-=s.first,p+=lowbit(p);
p=s.second+1;while(p<=n)B1[p]++,B2[p]+=s.second,p+=lowbit(p);
}
p=i+1;while(p<=n)B1[p]++,B2[p]+=i,p+=lowbit(p);
for(auto q:Q[i])
{
p=R[q];while(p)Ans[q]+=B1[p]*R[q]-B2[p],p-=lowbit(p);
}
}
for(uint i=0;i<q;i++)printf("%llu\n",Ans[i]);
return 0;
}