#include <bits/stdc++.h>
#define int long long
#define double long double
#pragma GCC optimize(2)
using namespace std;
const int N = 1e5 + 10, MOD = 998244353, INF = 1e9;
const double eps = 1e-17;

int Q_pow(int a, int b){
    int ans = 1, p = a;
    while(b){
        if(b & 1) ans = (ans * p) % MOD;
        b >>= 1;
        p = (p * p) % MOD;
    }
    return ans;
}

int t;
int n, m, val;
string s, ss;

struct Node{
	int son[26];
	int fail, ed;
}tr[N];
int cnt, sum[N], v[N][26];
queue <int> q;

void Insert(string s, int v){
	int p = 0;
	for(auto i : s){
		int ch = i - 'a';
		if(!tr[p].son[ch]) tr[p].son[ch] = ++cnt;
		p = tr[p].son[ch];
	}
	tr[p].ed += v;
}

void Get_fail(){
	for(int i = 0; i < 26; i++){
		if(tr[0].son[i]){
			q.push(tr[0].son[i]);
		}
	}

	while(!q.empty()){
		int tp = q.front();
		q.pop();

		sum[tp] = sum[tr[tp].fail] + tr[tp].ed;
		for(int i = 0; i < 26; i++){
			if(tr[tp].son[i]){
				tr[tr[tp].son[i]].fail = tr[tr[tp].fail].son[i];
				q.push(tr[tp].son[i]);
			}else{
				tr[tp].son[i] = tr[tr[tp].fail].son[i];
			}
		}
	}
}

double f[1001][4001];
int dp[1001][4001], len[1001][4001];

bool Check(double lim){

	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= cnt; j++){
			f[i][j] = -INF;
			dp[i][j] = 0;
			len[i][j] = 0;
		}
	}
	
	f[0][0] = 0;
	dp[0][0] = 0;
	len[0][0] = 0;

	for(int i = 0; i < n; i++){
		for(int j = 0; j <= cnt; j++){
			f[i + 1][j] = f[i][j];
			dp[i + 1][j] = dp[i][j];
			len[i + 1][j] = len[i][j];
		}
		for(int j = 0; j <= cnt; j++){
			int ch = s[i] - 'a';
			int to = tr[j].son[ch];

			if(!to) continue;
			if(f[i + 1][to] + eps < f[i][j] + sum[to] - lim){
				f[i + 1][to] = f[i][j] + sum[to] - lim;
				dp[i + 1][to] = dp[i][j] + sum[to];
				len[i + 1][to] = len[i][j] + 1;
			}
		}
	}

	for(int i = 1; i <= cnt; i++){
		if(f[n][i] >= 0){
			// printf("%.4Lf\n", f[n][i]);
			return 1;
		}
	}
	return 0;
}

signed main(){
	// freopen("1.in", "r", stdin);

	cin >> t;

	while(t--){
		cin >> n >> m >> s;
		
		for(int i = 1; i <= m; i++){
			cin >> ss >> val;
			Insert(ss, val);
		}
		Get_fail();

		// for(int i = 0; i <= cnt; i++){
		// 	cout << sum[i] << " ";
		// }
		// cout << "\n";

		double l = 0, r = 2e8, ans = 0;

		for(int i = 1; i <= 50; i++){
			double mid = (l + r) / 2;
			if(Check(mid)){
				ans = mid;
				l = mid + 1;
			}else{
				r = mid - 1;
			}
		}

		// printf("%.4Lf\n", ans);
		Check(ans);
		
		for(int i = 1; i <= cnt; i++){
			if(f[n][i] >= 0){
				int ret = dp[n][i] * Q_pow(len[n][i], MOD - 2) % MOD;
				cout << ret << "\n";
			}
		}

		for(int i = 0; i <= cnt; i++){
			memset(tr[i].son, 0, sizeof(tr[i].son));
			tr[i].ed = tr[i].fail = 0;
			sum[i] = 0;
		}
	}
}