#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1010;
const int maxm = 4040;
const ll mod = 998244353;

inline ll qpow(ll b, ll p) {
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

int n, m, f[maxm], nt, fail[maxm], ch[maxm][26], nxt[maxn][26];
char s[maxn], t[maxm];

db g[maxn][maxm];

inline bool check(db x) {
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= nt; ++j) {
			g[i][j] = -1e18;
		}
	}
	g[0][0] = 0;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= nt; ++j) {
			if (g[i][j] < -1e17) {
				continue;
			}
			if (g[i][j] > 1e-6) {
				return 1;
			}
			for (int k = 0; k < 26; ++k) {
				if (nxt[i + 1][k] <= n) {
					int ni = nxt[i + 1][k], nj = ch[j][k];
					g[ni][nj] = max(g[ni][nj], g[i][j] + f[nj] - x);
				}
			}
		}
	}
	return 0;
}

inline void build() {
	queue<int> q;
	for (int i = 0; i < 26; ++i) {
		if (ch[0][i]) {
			q.push(ch[0][i]);
		}
	}
	while (q.size()) {
		int u = q.front();
		q.pop();
		f[u] += f[fail[u]];
		for (int i = 0; i < 26; ++i) {
			if (ch[u][i]) {
				fail[ch[u][i]] = ch[fail[u]][i];
				q.push(ch[u][i]);
			} else {
				ch[u][i] = ch[fail[u]][i];
			}
		}
	}
}

void solve() {
	for (int i = 0; i <= nt; ++i) {
		mems(ch[i], 0);
		f[i] = fail[i] = 0;
	}
	nt = 0;
	scanf("%d%d%s", &n, &m, s + 1);
	for (int i = 0; i < 26; ++i) {
		nxt[n + 1][i] = n + 1;
	}
	for (int i = n; i; --i) {
		for (int j = 0; j < 26; ++j) {
			nxt[i][j] = nxt[i + 1][j];
		}
		nxt[i][s[i] - 'a'] = i;
	}
	while (m--) {
		int x, p = 0;
		scanf("%s%d", t, &x);
		for (int i = 0; t[i]; ++i) {
			if (!ch[p][t[i] - 'a']) {
				ch[p][t[i] - 'a'] = ++nt;
			}
			p = ch[p][t[i] - 'a'];
		}
		f[p] += x;
	}
	build();
	db l = 0, r = 1e8;
	while (r - l > 1e-6) {
		db mid = (l + r) / 2;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	int p = 1;
	for (int i = 2; i <= n; ++i) {
		if (fabs(l * i - round(l * i)) < fabs(l * p - round(l * p))) {
			p = i;
		}
	}
	ll x = round(l * p);
	printf("%lld\n", x % mod * qpow(p, mod - 2) % mod);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}