#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

const int N = 4007;
const int M = 1007;
const int mod = 998244353;

template<typename T>
inline bool getmax(T &a, T b) {return (a < b ? (a = b, true) : false);}

inline int fpow(int x, int t = mod - 2) {
	int res = 1;
	for (; t; t >>= 1, x = 1ll * x * x % mod)
		if (t & 1) res = 1ll * res * x % mod;
	return res;
}

const double eps = 1e-8;

struct Trie_Graph {
	int rt = 0, cnt = 0, fail[N];
	int son[N][26], nxt[N][26];
	// son = structure of the Trie
	// nxt = fill the trie in to trie graph
	int w[N];
	void reset() {
		rt = cnt = 0;
		memset(son[0], 0, sizeof(son[0]));
		memset(nxt[0], 0, sizeof(nxt[0]));
	}
	int newnode() {
		++cnt;
		fail[cnt] = w[cnt] = 0;
		memset(son[cnt], 0, sizeof(son[cnt]));
		memset(nxt[cnt], 0, sizeof(nxt[cnt]));
		return cnt;
	}
	int insert(int pre, int ch) {
		return son[pre][ch] ? son[pre][ch] : son[pre][ch] = newnode();
	}
	void insert(string &S) {
		int nw = rt;
		for (auto &ch : S) nw = insert(nw, ch - 'a');
		cin >> w[nw];
	}
	void build() {
		queue<int> Q;
		Q.push(rt);
		memcpy(nxt[rt], son[rt], sizeof(son[rt]));
		while (!Q.empty()) {
			int u = Q.front(); Q.pop();
			rep(ch, 0, 25) {
				int v = son[u][ch];
				if (!v) continue; 
				fail[v] = (u == 0 ? 0 : nxt[fail[u]][ch]);
				w[v] += w[fail[v]];
				memcpy(nxt[v], nxt[fail[v]], sizeof(nxt[v]));
				rep(cc, 0, 25) if (son[v][cc]) nxt[v][cc] = son[v][cc];
				Q.push(v);
			}
		}
	}

	double mx[M][N];

	int cur[M][N];

	pii pre[M][N], anspos;

	inline bool check(double val, string &S) {
		mx[0][rt] = cur[0][rt] = 0;
		rep(i, 1, cnt) mx[0][i] = -1e18, cur[0][i] = 0, pre[0][i] = {0, 0};
		int pos = 0;
		for (auto &ch : S) {
			int x = ch - 'a';
			rep(u, 0, cnt) {
				mx[pos + 1][u] = mx[pos][u];
				cur[pos + 1][u] = cur[pos][u];
				pre[pos + 1][u] = pre[pos][u];
			}
			rep(u, 0, cnt) {
				int v = nxt[u][x];
				if (getmax(mx[pos + 1][v], mx[pos][u] + w[v] - val)) {
					cur[pos + 1][v] = pos + 1;
					pre[pos + 1][v] = {cur[pos][u], u};
					if (mx[pos + 1][v] > eps) {anspos = {pos + 1, v}; return true;}
				}
			}
			++pos;
		}
		return false;
	}

	inline int run(string &S) {
		int sum = 0, nw = rt;
		for (auto &ch : S) {
			nw = nxt[nw][ch - 'a'];
			sum = (sum + w[nw]) % mod;
		}
		return 1ll * sum * fpow(S.length()) % mod;
	}

} tg;

inline void work() {
	
	tg.reset();
	int n, m; cin >> n >> m;
	string S, T; cin >> S;
	rep(i, 1, m) {cin >> T; tg.insert(T);}
	tg.build();

	double l = 0, r = 1e8;
	while (r - l > eps) {
		double mid = (l + r) / 2;
		tg.check(mid, S) ? l = mid : r = mid;
	}
	tg.check(l, S);

	int sum = 0, len = 0;
	auto [pos, cur] = tg.anspos;
	do {
		++len;
		sum = (sum + tg.w[cur]) % mod;
		auto [_pos, _cur] = tg.pre[pos][cur];
		swap(pos, _pos);
		swap(cur, _cur);
	} while (pos);

	cout << 1ll * sum * fpow(len) % mod << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int t; cin >> t;
	while (t--) work();
	return 0;
}