#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define Mp make_pair
#define PR pair<int, pair<int,int> >
#define fi first
#define se second
#define pb push_back
typedef long long ll;
using namespace std;

int rd() {
	int r = 0; bool w = false; char ch = getchar();
	while( ch < '0' || ch > '9' ) w = !(ch^45), ch = getchar();
	while( ch >= '0' && ch <= '9' ) r = (r<<1) + (r<<3) + (ch^48), ch = getchar();
	return w ? -r : r;
}

#define MAXN 1000
#define MAXM 1000
#define MAXS 4000
#define MAXW 4000
const int mod = 998244353;
inline int quick_pow( int a , int p ) {
	int ret = 1;
	for(;p;p>>=1) {
		if( p & 1 ) ret = 1ll * ret * a % mod;
		a = 1ll * a * a % mod;
	}
	return ret;
}
char *w[MAXM+5]; char wbuf[MAXW+5], s[MAXN+5];
const double INF = 1e20;
const double eps = 1e-10;
int n, m;
struct AC{
	int t[MAXS+5][26], tot;
	int fail[MAXS+5], val[MAXS+5]; vector<int> to[MAXS+5];
	double dp[2][MAXS+5];
	double f[MAXN+5][MAXS+5];
	int g[MAXN+5][MAXS+5];
	void clear() {
		FOR(i,0,tot) {
			memset(t[i], 0, sizeof(t[i]));
			fail[i] = val[i] = 0;
			to[i].clear();
		}
		tot = 0;
	}
	void insert( char *s , int V ) {
		int len = strlen(s+1);
		int u = 0;
		FOR(i,1,len) {
			if( !t[u][s[i]-'a'] ) t[u][s[i]-'a'] = ++tot;
			u = t[u][s[i] - 'a'];
		}
		val[u] = V;
	}
	void dfs( int u ) {
		for(auto v: to[u]) {
			val[v] += val[u];
			dfs(v);
		}
	}
	void build() {
		queue<int> q; while( !q.empty() ) q.pop();
		FOR(i,0,25) if( t[0][i] ) q.push(i), fail[t[0][i]] = 0;
		while( !q.empty() ) {
			int u = q.front(); q.pop();
			FOR(i,0,25) {
				if( t[u][i] ) fail[t[u][i]] = t[fail[u]][i], to[t[fail[u]][i]].pb(t[u][i]);
				else t[u][i] = t[fail[u]][i];
			}
		}
		dfs(0);
	}
	bool chk( double x ) {
		int r = 0;
		FOR(i,0,tot) dp[r][i] = -INF;
		dp[r][0] = -eps;
		FOR(i,1,n) {
			memcpy(dp[r^1], dp[r], sizeof(dp[r]));
			int k = s[i] - 'a';
			FOR(j,0,tot) {
				dp[r^1][t[j][k]] = max(dp[r^1][t[j][k]], dp[r][j] + val[t[j][k]] - x);
			}
			r ^= 1;
		}
		FOR(i,0,tot) if( dp[r][i] > 0 ) return true;
		return false;
	}
	int getm( double x ) {
		FOR(i,0,tot) f[0][i] = -INF;
		f[0][0] = -eps;
		FOR(i,1,n) {
			memcpy(f[i], f[i-1], sizeof(f[i]));
			memset(g[i], -1, sizeof(g[i]));
			int k = s[i] - 'a';
			FOR(j,0,tot) {
				if( f[i][t[j][k]] < f[i-1][j] + val[t[j][k]] - x )
					f[i][t[j][k]] = f[i-1][j] + val[t[j][k]] - x,
					g[i][t[j][k]] = j;
			}
		}
		int pos;
		FOR(i,0,tot) if( f[n][i] >= 0 ) pos = i;
		ll now = 0, len = 0;
		ROF(i,n,1) {
			now += (g[i][pos] != -1) ? val[pos] : 0;
			len += (g[i][pos] != -1) ? 1 : 0;
			pos = (g[i][pos] == -1) ? pos : g[i][pos];
		}
		return 1ll * now * quick_pow(len, mod-2) % mod;
	}
}K;
void solve() {
	n = rd(), m = rd();
	K.clear();
	scanf("%s", s+1);
	w[1] = wbuf; scanf("%s", w[1]+1);
	K.insert(w[1], rd());
	FOR(i,2,m) {
		w[i] = w[i-1] + strlen(w[i-1]);
		*w[i] = 0;
		scanf("%s", w[i] + 1);
		K.insert(w[i], rd());
	}
	K.build();
	double l = 0, r = INF, arge = 0;
	while( r - l > eps ) {
		double mid = (l + r) / 2;
		if( K.chk(mid) ) {
			l = mid; arge = mid;
		} else r = mid;
	}
	printf("%d\n", K.getm(arge));
}

int main() {
	int T = rd(); while( T-- ) solve();
	return 0;
}