#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int mod = 998244353;
const double inf = 1e18;
int qp(int p,int q){
	int ans = 1,pro = p;
	while(q){
		if(q&1)ans = ans*pro%mod;
		pro = pro*pro%mod;q>>=1;
	}
	return ans;
}
int n,m;
char s[10005];int nw;
int trie[10005][26],fail[10005],v[10005];
vector<int>p[10005];
void ins(string s,int c){
	int now =0 ;
	for(int i =0;i<s.size();i++){
		if(!trie[now][s[i]-'a'])trie[now][s[i]-'a'] = ++nw;
		now = trie[now][s[i]-'a'];
	}
	v[now]+=c;
}
void dfs(int now,int fa){
	if(now!=fa)v[now]+=v[fa];
	for(auto x:p[now])dfs(x,now);
}
void build(){
	queue<int>q;
	for(int i =0;i<26;i++)if(trie[0][i])q.push(trie[0][i]);
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i =0;i<26;i++){
			if(trie[now][i]){
				q.push(trie[now][i]);
				fail[trie[now][i]] = trie[fail[now]][i];
			}else{
				trie[now][i] = trie[fail[now]][i];
			}
		}
	}
	for(int i =1;i<=nw;i++)p[fail[i]].push_back(i);
	dfs(0,0);
}
double dp[1005][4005];int pre[1005][4005];
bool check(double x){
	for(int i =0;i<=n;i++)for(int j =0;j<=nw;j++)dp[i][j] = -inf;
	dp[0][0] = 0;
	for(int i = 0;i<n;i++){
		for(int j =0;j<=nw;j++){
			if(dp[i][j] == -inf)continue;
			if(dp[i+1][j]<dp[i][j]){
				dp[i+1][j] = dp[i][j];pre[i+1][j] = j;
			}
			int c = s[i+1]-'a',to = trie[j][c];
			if(dp[i+1][to]<dp[i][j]+v[to]-x){
				dp[i+1][to]=dp[i][j]+v[to]-x;
				pre[i+1][to] = j;
			}
		}
	}
	double mx = -inf;
	for(int i =0;i<=nw;i++)mx = max(mx,dp[n][i]);
	return (mx>0);
}
void solve(){
	for(int i =0;i<=nw;i++)fail[i] = 0,v[i] =0,p[i].clear();
	for(int i =0;i<=nw;i++)for(int j =0;j<26;j++)trie[i][j] = 0;
	nw = 0;
	cin >> n >> m;for(int i = 1;i<=n;i++)cin >> s[i];
	int sum = 0;
	for(int i = 1;i<=m;i++){
		string s;cin >> s;int c;cin >> c;
		ins(s,c);sum+=c;
	}
	build();
	double l = 0,r = sum;
	for(int i =0;i<60;i++){
		double mid = (l+r)/2;
		if(check(mid))l = mid;
		else r = mid;
	}
	check(l);
	int tot=0,s = 0;
	double mx =0;int mxpos = 0;
	for(int i =0;i<=nw;i++)if(dp[n][i]>mx)mx =dp[n][i],mxpos = i;
	for(int i = n;i>=1;i--){
		int to = pre[i][mxpos];
		if(mxpos != to)++tot,s+=v[mxpos];
		mxpos = to;
	}
	s%=mod;
//	cout << tot << " " << s << endl;
	cout << s*qp(tot,mod-2)%mod << endl;
}
signed main(){
	int t;cin >> t;
	while(t--){
		solve();
	}
	return 0;
}/*
3
 17 3
 woyaoakccpcxiamen
 ak 5
 ccpc 6
 xiamen 8
 33 3
 niweishenmezhengtianxunlianbuliwo
 wo 3
 se 1
 zayin 7
 39 2
 programmingcontestandmewhichisimportant
 me 11
 gg 2
*/