#include<bits/stdc++.h>
using namespace std;
const int N=100010,base=41,mod=1e9+9;
string s[N];
int maxx[N],pw[N];
vector<int>las[N];
vector<pair<int,int> >lyndon[N];
struct hs{
	vector<int>p;
	void set(string& s){
		int n=s.length();
		p.resize(n);
		p[0]=s[0];
		for(int i=1;i<=n-1;i++){
			p[i]=(1ll*p[i-1]*base+s[i])%mod;
		}
	}
	int get(int l,int r){
		if(l==0){
			return p[r];
		}
		return (p[r]-1ll*p[l-1]*pw[r-l+1]%mod+mod)%mod;
	}
}p[N];
void Lyndon(int i,string& s){
	int n=s.length(),x=0,y,z;
	maxx[i]=0;
	las[i].clear();
	lyndon[i].clear();
	while(x<=n-1){
		y=x;
		z=x+1;
		while(s[y]<=s[z]){
			if(s[y]==s[z]){
				y++;
				z++;
			}
			else{
				y=x;
				z++;
			}
		}
		if(z==n){
			las[i].push_back(x);
		}
		while(x<=y){
			lyndon[i].push_back({x,x+z-y-1});
			x+=(z-y);
		}
		maxx[i]=max(maxx[i],z-y);
	}
	las[i].push_back(n);
}
int calc(int x,int y,int a,int len){
	if(a+len-1<s[x].length()){
		return p[x].get(a,a+len-1);
	}
	if(a>=s[x].length()){
		return p[y].get(a-s[x].length(),a-s[x].length()+len-1);
	}
	return (1ll*p[x].get(a,s[x].length()-1)*pw[a+len-s[x].length()]%mod+p[y].get(0,a-s[x].length()+len-1))%mod;
}
char get(int x,int y,int a){
	if(a<s[x].length()){
		return s[x][a];
	}
	return s[y][a-s[x].length()];
}
bool check(int x,int y,int a,int b,int len){
	int l=1,r=len,mid,ans=0;
	if(calc(x,y,a,len)==calc(x,y,b,len)){
		return 0;
	}
	while(l<=r){
		mid=(l+r)>>1;
		if(calc(x,y,a,mid)==calc(x,y,b,mid)){
			l=mid+1;
			ans=mid;
		}
		else{
			r=mid-1;
		}
	}
	return get(x,y,a+ans)<get(x,y,b+ans);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,n,m,x,y,a,b,now,ans,l,r,mid,anss;
	cin>>t;
	for(int i=1;i<=100000;i++){
		pw[i]=1ll*pw[i-1]*base%mod;
	}
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>s[i];
			Lyndon(i,s[i]);
			p[i].set(s[i]);
		}
		while(m--){
			scanf("%d%d",&x,&y);
			now=-1;
			ans=max(maxx[x],maxx[y]);
			for(int i=0;i<las[x].size()-1;i++){
				a=las[x][i];
				b=las[x][i+1];
				if(check(x,y,a,b,s[x].length()-b+s[y].length())){
					now=a;
					break;
				}
			}
			if(now!=-1){
				l=0;
				r=lyndon[y].size()-1;
				while(l<=r){
					mid=(l+r)>>1;
					if(check(x,y,now,s[x].length()+lyndon[y][mid].first,lyndon[y][mid].second-lyndon[y][mid].first+1)){
						l=mid+1;
						anss=lyndon[y][mid].second+1;
					}
					else{
						r=mid-1;
					}
				}
				ans=max(ans,(int)s[x].length()-now+anss);
			}
			cout<<ans<<"\n";
		}
	}
}