#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5,Mod=1e9+7;
int T,nxt[N],fa[N][21],sum[N];
string s;
int search(int x){
	//找第一个大于x/2
	
	int tmp = x;
	for(int j=20;j>=0;j--){
		if(fa[x][j]>tmp/2)x=fa[x][j];
	}
	return fa[x][0];
}
int main(){
	cin>>T;
	while(T--){
		cin>>s;s="#"+s;
		for(int j=0,i=2;i<s.size();i++){
			while(j&&s[j+1]!=s[i])j=nxt[j];
			if(s[j+1]==s[i])j++;
			nxt[i] = j;
		}
		for(int i=1;i<s.size();i++){
			fa[i][0] = nxt[i];
			sum[i] = sum[nxt[i]]+1;
			for(int j=1;j<=20;j++){
				fa[i][j] = fa[fa[i][j-1]][j-1];
			}
		}
		long long res = 1;
		for(int i=1;i<s.size();i++){
			int t = search(i);
		//	cout<<t<<endl;
			res*=(sum[t]+1);
			res%=Mod;
		}
		cout<<res<<endl;
	}
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,m,fa[N][21],nxt[N],dep[N];
string s;
int lca(int x,int y){
	//1.将xy跳到同层
	if(dep[x]>dep[y])swap(x,y);
	for(int j=20;j>=0;j--){
		if(dep[fa[y][j]]>=dep[x])y=fa[y][j];
	}
	if(x==y)return fa[x][0];
	
	for(int j=20;j>=0;j--){
		if(fa[x][j]!=fa[y][j]){
			x=fa[x][j];
			y=fa[y][j];
		}
	}
	return fa[x][0];
}
int main(){
	cin>>s;s="#"+s;
	for(int j=0,i=2;i<s.size();i++){
		while(j && s[j+1]!=s[i])j=nxt[j];
		if(s[j+1]==s[i])j++;
		nxt[i] = j;
	}
	for(int i=1;i<s.size();i++){
		dep[i] = dep[nxt[i]]+1;
		fa[i][0] = nxt[i];
		for(int j=1;j<=20;j++){
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	cin>>m;
	while(m--){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
	return 0;
}