#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=500010;
int sz,last,go[N][4],len[N],diff[N],link[N],series_link[N],baby[N];
int n,m,i,j,k,x,y,f[N],bit[N];
int ans[N];
vector<pair<int,int> >poses[N],que[N];
char s[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int go_until_pal(int i,int v){
  while(s[i]!=s[i-len[v]-1])v=link[v];
  return v;
}
inline pair<vector<int>,vector<int> >add_char(int i){
  last=go_until_pal(i,last);
  int&v=go[last][s[i]-'a'];
  if(v==-1){
    v=sz++;
    len[v]=len[last]+2;
    if(!last)link[v]=1;
    else{
      last=go_until_pal(i,link[last]);
      link[v]=go[last][s[i]-'a'];
    }
    diff[v]=len[v]-len[link[v]];
    if(diff[v]==diff[link[v]]){
      baby[v]=baby[link[v]];
      series_link[v]=series_link[link[v]];
    }else{
      baby[v]=v;
      series_link[v]=link[v];
    }
  }
  last=v;
  pair<vector<int>,vector<int> >ans;
  for(int u=v;u!=1;u=series_link[u]){
    int B=baby[u];
    vector<pair<int,int> >&vec=poses[B];
    int left=i-len[u]+1;
    if(vec.size()&&vec.back().first==left)vec.back().second=len[u];
    else vec.push_back(make_pair(left,len[u]));
    ans.first.push_back(i-len[B]+1);
    if(vec.size()!=1){
      int L=vec[vec.size()-2].first,
          len_=vec[vec.size()-2].second,
          R=L+len_-1,
          L_=R-len[u]+1;
      ans.second.push_back(L_);
    }
    if(vec.size()!=1)if(vec[vec.size()-1].second==vec[vec.size()-2].second){
      vec[vec.size()-2]=vec[vec.size()-1];
      vec.pop_back();
    }
  }
  return ans;
}
inline void add(int x,int p){for(f[x]+=p;x<=n;x+=x&-x)bit[x]+=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
int main(){
  scanf("%s%d",s+1,&m);
  n=strlen(s+1);
  for (int i=1;i<=n;++i){
	  if(s[i]=='A')s[i]='a';
	  if(s[i]=='G')s[i]='b';
	  if(s[i]=='C')s[i]='c';
	  if(s[i]=='T')s[i]='d';
  }
  sz=2,last=0,len[0]=-1;
  for(i=0;i<=n+5;i++)memset(go[i],-1,sizeof(go[i]));
  for(i=0;i<m;i++){
    read(x),read(y);
    que[y].push_back(make_pair(x,i));
  }
  for(i=1;i<=n;i++){
    pair<vector<int>,vector<int> >vec=add_char(i);
    vector<int>adding=vec.first,deleting=vec.second;
    for(j=0;j<deleting.size();j++){
      if(!f[k=deleting[j]])continue;
      add(k,-1);
    }
    for(j=0;j<adding.size();j++){
      if(f[k=adding[j]]==1)continue;
      add(k,1);
    }
    for(j=0;j<que[i].size();j++)ans[que[i][j].second]=sz-2-ask(que[i][j].first-1);
  }
  for(i=0;i<m;i++)printf("%d\n",ans[i]);
}
/*#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=500010;
int sz,last,go[N][4],len[N],diff[N],link[N],series_link[N],baby[N];
int n,m,i,j,k,x,y,f[N],bit[N];
int ans[N];
vector<pair<int,int> >poses[N],que[N];
char s[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int go_until_pal(int i,int v){
  while(s[i]!=s[i-len[v]-1])v=link[v];
  return v;
}
inline pair<vector<int>,vector<int> >add_char(int i){
  last=go_until_pal(i,last);
  int&v=go[last][s[i]-'a'];
  if(v==-1){
    v=sz++;
    len[v]=len[last]+2;
    if(!last)link[v]=1;
    else{
      last=go_until_pal(i,link[last]);
      link[v]=go[last][s[i]-'a'];
    }
    diff[v]=len[v]-len[link[v]];
    if(diff[v]==diff[link[v]]){
      baby[v]=baby[link[v]];
      series_link[v]=series_link[link[v]];
    }else{
      baby[v]=v;
      series_link[v]=link[v];
    }
  }
  last=v;
  pair<vector<int>,vector<int> >ans;
  for(int u=v;u!=1;u=series_link[u]){
    int B=baby[u];
    vector<pair<int,int> >&vec=poses[B];
    int left=i-len[u]+1;
    if(vec.size()&&vec.back().first==left)vec.back().second=len[u];
    else vec.push_back(make_pair(left,len[u]));
    ans.first.push_back(i-len[B]+1);
    if(vec.size()!=1){
      int L=vec[vec.size()-2].first,
          len_=vec[vec.size()-2].second,
          R=L+len_-1,
          L_=R-len[u]+1;
      ans.second.push_back(L_);
    }
    if(vec.size()!=1)if(vec[vec.size()-1].second==vec[vec.size()-2].second){
      vec[vec.size()-2]=vec[vec.size()-1];
      vec.pop_back();
    }
  }
  return ans;
}
inline void add(int x,int p){for(f[x]+=p;x<=n;x+=x&-x)bit[x]+=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
int main(){
  scanf("%s%d",s+1,&m);
  n=strlen(s+1);
  for (int i=1;i<=n;++i){
	  if(s[i]=='A')s[i]='a';
	  if(s[i]=='G')s[i]='b';
	  if(s[i]=='C')s[i]='c';
	  if(s[i]=='T')s[i]='d';
  }
  sz=2,last=0,len[0]=-1;
  for(i=0;i<=n+5;i++)memset(go[i],-1,sizeof(go[i]));
  for(i=0;i<m;i++){
    read(x),read(y);
    que[y].push_back(make_pair(x,i));
  }
  for(i=1;i<=n;i++){
    pair<vector<int>,vector<int> >vec=add_char(i);
    vector<int>adding=vec.first,deleting=vec.second;
    for(j=0;j<deleting.size();j++){
      if(!f[k=deleting[j]])continue;
      add(k,-1);
    }
    for(j=0;j<adding.size();j++){
      if(f[k=adding[j]]==1)continue;
      add(k,1);
    }
    for(j=0;j<que[i].size();j++)ans[que[i][j].second]=sz-2-ask(que[i][j].first-1);
  }
  for(i=0;i<m;i++)printf("%d\n",ans[i]);
}#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=500010;
int sz,last,go[N][4],len[N],diff[N],link[N],series_link[N],baby[N];
int n,m,i,j,k,x,y,f[N],bit[N];
int ans[N];
vector<pair<int,int> >poses[N],que[N];
char s[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int go_until_pal(int i,int v){
  while(s[i]!=s[i-len[v]-1])v=link[v];
  return v;
}
inline pair<vector<int>,vector<int> >add_char(int i){
  last=go_until_pal(i,last);
  int&v=go[last][s[i]-'a'];
  if(v==-1){
    v=sz++;
    len[v]=len[last]+2;
    if(!last)link[v]=1;
    else{
      last=go_until_pal(i,link[last]);
      link[v]=go[last][s[i]-'a'];
    }
    diff[v]=len[v]-len[link[v]];
    if(diff[v]==diff[link[v]]){
      baby[v]=baby[link[v]];
      series_link[v]=series_link[link[v]];
    }else{
      baby[v]=v;
      series_link[v]=link[v];
    }
  }
  last=v;
  pair<vector<int>,vector<int> >ans;
  for(int u=v;u!=1;u=series_link[u]){
    int B=baby[u];
    vector<pair<int,int> >&vec=poses[B];
    int left=i-len[u]+1;
    if(vec.size()&&vec.back().first==left)vec.back().second=len[u];
    else vec.push_back(make_pair(left,len[u]));
    ans.first.push_back(i-len[B]+1);
    if(vec.size()!=1){
      int L=vec[vec.size()-2].first,
          len_=vec[vec.size()-2].second,
          R=L+len_-1,
          L_=R-len[u]+1;
      ans.second.push_back(L_);
    }
    if(vec.size()!=1)if(vec[vec.size()-1].second==vec[vec.size()-2].second){
      vec[vec.size()-2]=vec[vec.size()-1];
      vec.pop_back();
    }
  }
  return ans;
}
inline void add(int x,int p){for(f[x]+=p;x<=n;x+=x&-x)bit[x]+=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
int main(){
  scanf("%s%d",s+1,&m);
  n=strlen(s+1);
  for (int i=1;i<=n;++i){
	  if(s[i]=='A')s[i]='a';
	  if(s[i]=='G')s[i]='b';
	  if(s[i]=='C')s[i]='c';
	  if(s[i]=='T')s[i]='d';
  }
  sz=2,last=0,len[0]=-1;
  for(i=0;i<=n+5;i++)memset(go[i],-1,sizeof(go[i]));
  for(i=0;i<m;i++){
    read(x),read(y);
    que[y].push_back(make_pair(x,i));
  }
  for(i=1;i<=n;i++){
    pair<vector<int>,vector<int> >vec=add_char(i);
    vector<int>adding=vec.first,deleting=vec.second;
    for(j=0;j<deleting.size();j++){
      if(!f[k=deleting[j]])continue;
      add(k,-1);
    }
    for(j=0;j<adding.size();j++){
      if(f[k=adding[j]]==1)continue;
      add(k,1);
    }
    for(j=0;j<que[i].size();j++)ans[que[i][j].second]=sz-2-ask(que[i][j].first-1);
  }
  for(i=0;i<m;i++)printf("%d\n",ans[i]);
}#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=500010;
int sz,last,go[N][4],len[N],diff[N],link[N],series_link[N],baby[N];
int n,m,i,j,k,x,y,f[N],bit[N];
int ans[N];
vector<pair<int,int> >poses[N],que[N];
char s[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int go_until_pal(int i,int v){
  while(s[i]!=s[i-len[v]-1])v=link[v];
  return v;
}
inline pair<vector<int>,vector<int> >add_char(int i){
  last=go_until_pal(i,last);
  int&v=go[last][s[i]-'a'];
  if(v==-1){
    v=sz++;
    len[v]=len[last]+2;
    if(!last)link[v]=1;
    else{
      last=go_until_pal(i,link[last]);
      link[v]=go[last][s[i]-'a'];
    }
    diff[v]=len[v]-len[link[v]];
    if(diff[v]==diff[link[v]]){
      baby[v]=baby[link[v]];
      series_link[v]=series_link[link[v]];
    }else{
      baby[v]=v;
      series_link[v]=link[v];
    }
  }
  last=v;
  pair<vector<int>,vector<int> >ans;
  for(int u=v;u!=1;u=series_link[u]){
    int B=baby[u];
    vector<pair<int,int> >&vec=poses[B];
    int left=i-len[u]+1;
    if(vec.size()&&vec.back().first==left)vec.back().second=len[u];
    }
    for(j=0;j<que[i].size();j++)ans[que[i][j].second]=sz-2-ask(que[i][j].first-1);
  }
  for(i=0;i<m;i++)printf("%d\n",ans[i]);
}*/