#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int INF = 0x3f3f3f3f;
const int mods = 998244353;
const double eps = 1e-5;
typedef long long ll;

int n, m, nodenum;
int ch[MAXN][26], fa[MAXN];
char st[MAXN], ST[MAXN];
ll A[MAXN], s[MAXN][26];
queue<int> que;

void Init() {
	for (int i = 1; i <= nodenum ; ++ i) {
		fa[i] = A[i] = 0;
		for (int j = 0; j < 26 ; ++ j) ch[i][j] = s[i][j] = 0;
	}
	nodenum = 1;
}
int quick_pow(int x, int y) {
	int ret = 1;
	for (; y ; y >>= 1) {
		if (y & 1) ret = 1ll * ret * x % mods;
		x = 1ll * x * x % mods;
	}
	return ret;
}
void insert(char *st, int c) {
	int len = strlen(st), nw = 1;
	for (int i = 0; i < len ; ++ i)  {
		if (!ch[nw][st[i] - 'a']) ch[nw][st[i] - 'a'] = ++ nodenum;
		nw = ch[nw][st[i] - 'a'];
	}
	A[nw] += c;
}
void Build() {
	for (int i = 1; i <= nodenum ; ++ i)
		for (int j = 0; j < 26 ; ++ j)
			if (ch[i][j]) s[i][j] = A[ch[i][j]];
	fa[1] = 1;
	for (int i = 0; i < 26 ; ++ i)
		if (ch[1][i]) fa[ch[1][i]] = 1, que.push(ch[1][i]);
		else ch[1][i] = 1;
	while (!que.empty()) {
		int q = que.front(); que.pop();
		for (int i = 0; i < 26 ; ++ i) {
			if (ch[q][i]) fa[ch[q][i]] = ch[fa[q]][i], que.push(ch[q][i]);
			else ch[q][i] = ch[fa[q]][i];
			s[q][i] += s[fa[q]][i];
		}
	}
//	for (int i = 1; i <= nodenum ; ++ i)
//		for (int j = 0; j < 26 ; ++ j) 
//			if (s[i][j]) cout << i << " " << j << " " << ch[i][j] << " " << s[i][j] << endl;
}
double f[1005][4005];
int d[1005][4005];
ll g[1005][4005];

int check(double x) {
	for (int j = 1; j <= nodenum ; ++ j) f[0][j] = -1e60, g[0][j] = d[0][j] = 0;
	f[0][1] = 0;
	for (int i = 0; i < n ; ++ i) {
		for (int j = 1; j <= nodenum ; ++ j) {
			f[i + 1][j] = f[i][j];
			g[i + 1][j] = g[i][j];
			d[i + 1][j] = d[i][j];
		}
		for (int j = 1; j <= nodenum ; ++ j)
			if (f[i + 1][ch[j][st[i + 1] - 'a']] < f[i][j] + s[j][st[i + 1] - 'a'] - x) {
				f[i + 1][ch[j][st[i + 1] - 'a']] = f[i][j] + s[j][st[i + 1] - 'a'] - x; 
				g[i + 1][ch[j][st[i + 1] - 'a']] = g[i][j] + s[j][st[i + 1] - 'a']; 
				d[i + 1][ch[j][st[i + 1] - 'a']] = d[i][j] + 1;
			}
	}
//	for (int i = 1; i <= nodenum ; ++ i) 
//		cout << i << " " << f[n][i] << " " << d[n][i] << endl;
	for (int i = 1; i <= nodenum ; ++ i)
		if (f[n][i] > eps) return 1;
	return 0;
}

signed main() {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
#endif
	int Case;
	scanf("%d", &Case);
	while (Case --) {
		Init();
		scanf("%d%d", &n, &m);
		scanf("%s", st + 1);
		for (int i = 1; i <= m ; ++ i) {
			int x;
			scanf("%s%d", ST, &x);
			insert(ST, x);
		}
		Build();
		double l = 0, r = 100000;
		while (l + eps < r) {
			double mid = (l + r) * 0.5;
			if (check(mid)) l = mid;
			else r = mid;
		}
		check(l);

		int ans = 0;
		for (int i = 1; i <= nodenum ; ++ i)
			if (f[n][i] > eps) { ans = 1ll * g[n][i] * quick_pow(d[n][i], mods - 2) % mods; break; }
		printf("%d\n", ans);
	}
	return 0;
}