#include<bits/stdc++.h>
#define int long long
#define ld long double
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2000+10,MAXM=10000+10,MOD=998244353;
int T,n,m,v[MAXN],tot=1,tr[MAXM][27],fail[MAXM],pre[MAXM];
string S,w[MAXN];
int qpow(int base,int p) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return ans;
}
void insert(string S,int v) {
	int u=1;
	for(auto ch:S) {
		if(!tr[u][ch-'a']) tr[u][ch-'a']=++tot;
		u=tr[u][ch-'a'];
	}
	return pre[u]+=v,void();
}
void build(void) {
	queue<int> q;
	ffor(i,0,25) if(tr[1][i]) fail[tr[1][i]]=1,q.push(tr[1][i]);
	else tr[1][i]=1;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		pre[u]+=pre[fail[u]];
		ffor(i,0,25) if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
		else tr[u][i]=tr[fail[u]][i];
	}
	return ;
}
ld dp[2][MAXM];
int rl[2][MAXM],s[2][MAXM];
pair<ld,pair<int,int>> query(ld del) {
	ffor(i,1,tot) dp[0][i]=dp[1][i]=-10000000000,rl[0][i]=rl[1][i]=s[0][i]=s[1][i]=0;
	dp[0][1]=0;
	ffor(i,1,n) {
		ffor(j,1,tot) dp[i&1][j]=dp[(i-1)&1][j],rl[i&1][j]=rl[(i-1)&1][j],s[i&1][j]=s[(i-1)&1][j];
		ffor(j,1,tot) {
			int t=tr[j][S[i]-'a'];
			if(dp[(i-1)&1][j]+pre[t]-del>dp[i&1][t]) dp[i&1][t]=dp[(i-1)&1][j]+pre[t]-del,rl[i&1][t]=(rl[(i-1)&1][j]+pre[t])%MOD,s[i&1][t]=s[(i-1)&1][j]+1;
		}
	}
	ffor(i,1,tot) if(dp[n&1][i]>0) return {dp[n&1][i],{rl[n&1][i],s[n&1][i]}};
	return {0,{0,0}};
}
int solve(void) {
	ld L=0,R=300000000;
	int ans=0;
	while(R-L>1e-7) {
		ld mid=(L+R)/2;
		auto pr=query(mid);
		if(pr.first>0) ans=pr.second.first*qpow(pr.second.second,MOD-2)%MOD,L=mid;
		else R=mid;
	}
	return ans;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		cin>>n>>m>>S;	
		ffor(i,1,m) cin>>w[i]>>v[i];
		memset(tr,0,sizeof(tr)),memset(fail,0,sizeof(fail)),memset(pre,0,sizeof(pre)),tot=1;
		ffor(i,1,m) insert(w[i],v[i]);
		build();
		cout<<solve()<<'\n';
	}
	return 0;
}