#include<bits/stdc++.h>
#define N 4005
#define re
#define int long long
#define ll long long
#define P 998244353
using namespace std;
int n,m,K,q,T;
inline void Rd(int &res){
	re char c;res=0;
	while(c=getchar(),c<48);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
}
char c[N],s[N];
int to[N][30];
const double eps=1e-8;
int Pow(int x,int k){
	int res=1;
	while(k){
		if(k&1)res=1ll*res*x%P;
		x=1ll*x*x%P;
		k>>=1;
	}
	return res;
}
struct AC{
	#define M 10005
	int trie[M][26],V[M],fail[M],tot,Q[M];
	double f[4005],g[4005];
	int pre[1005][4005][2],pos[4005],pos1[4005],id[4005],id1[4005];
	void clear(){
		for(int i=0;i<=tot;i++){
			memset(trie[i],0,sizeof(trie[i]));
			V[i]=0;fail[i]=0;Q[i]=0;
		}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=tot;j++)
				pre[i][j][0]=pre[i][j][1]=0;
		tot=0;
	}
	void insert(){
		scanf("%s",c+1);
		int v;Rd(v);
		int len=strlen(c+1);
		int cur=0;
		for(int i=1;i<=len;i++){
			int t=c[i]-'a';
			if(!trie[cur][t])trie[cur][t]=++tot;
			cur=trie[cur][t];
		}
		V[cur]+=v;
	}
	void Build(){
		int l=0,r=0;
		for(re int i=0;i<26;i++)if(trie[0][i]){
			fail[trie[0][i]]=0;
			Q[++r]=trie[0][i];
		}
		while(l<r){
			int x=Q[++l];
			for(re int i=0;i<26;i++)
				if(trie[x][i])fail[trie[x][i]]=trie[fail[x]][i],Q[++r]=trie[x][i];
				else trie[x][i]=trie[fail[x]][i];
		}
		for(int i=1;i<=tot;i++)
			V[i]+=V[fail[i]];
	}
	
	bool check(double v){
		for(int j=0;j<=tot;j++)f[j]=-1e15;
		f[0]=0;
		for(int i=1;i<=n;i++){
			int t=s[i]-'a';
			for(int j=0;j<=tot;j++)g[j]=f[j];
			for(int j=0;j<=tot;j++){
				g[trie[j][t]]=max(g[trie[j][t]],f[j]+V[trie[j][t]]-v);
				
			}
			for(int j=0;j<=tot;j++)f[j]=g[j];
		}
		for(int i=1;i<=tot;i++)
			if(f[i]+eps>0)return 1;
		return 0;
	}
	
	void Get(double v){
		for(int j=0;j<=tot;j++)f[j]=-1e15,pos[j]=0;
		f[0]=0;
		for(int i=1;i<=n;i++){
			int t=s[i]-'a';
			for(int j=0;j<=tot;j++)g[j]=f[j],pos1[j]=pos[j];
			for(int j=0;j<=tot;j++){
				if(g[trie[j][t]]<f[j]+V[trie[j][t]]-v){
					g[trie[j][t]]=f[j]+V[trie[j][t]]-v;
					pre[i][trie[j][t]][0]=pos[j];
					pre[i][trie[j][t]][1]=j;
					pos1[trie[j][t]]=i;
				}
				
			}
			for(int j=0;j<=tot;j++)f[j]=g[j],pos[j]=pos1[j];
		}
		int t=0;
		for(int i=0;i<=tot;i++)
			if(f[i]>f[t])t=i;
		
		ll sum=0; int len=0;
		int x=pos[t];
		while(x){
			len++;
			sum+=V[t];
			int x1=pre[x][t][0],t1=pre[x][t][1];
			x=x1,t=t1;
		}
		len=Pow(len,P-2);
		sum=sum*len%P;
		printf("%lld\n",sum);
		
	}
}A;


signed main(){
	Rd(T);
	while(T--){
		Rd(n),Rd(m);
		scanf("%s",s+1);
		for(int i=1;i<=m;i++)A.insert();
		A.Build();
		for(int i=n;i>=1;i--){
			memcpy(to[i],to[i+1],sizeof(to[i]));
			to[i][s[i]-'a']=i;
		}
		
		int tim=200;
		double l=0,r=1e9,k=0;
		while(tim--){
			double mid=(l+r)*0.5;
			if(A.check(mid))k=mid,l=mid;
			else r=mid;
		}
//		printf("%.5lf\n",k);
//		A.Get(k);
		
		for(int i=1;i<=n;i++){
			int res=(int)(k*i+0.5);
			if(fabs(1.0*res/i-k)<1e-7){
				int v=Pow(i,P-2);
				res=1ll*res*v%P;
				printf("%lld\n",res);
				break;
			}
		}
		
		for(int i=0;i<=n;i++)memset(to[i],0,sizeof(to[i]));
		A.clear();
		
	}
	return 0;
}