#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
 
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 998244353;

int mult(int a, int b)
{
	return (LL)a * b % mod;
}

int binpow(int a, int n)
{
	int res = 1;
	while (n)
	{
		if (n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

const db LINF = 1e18;
const int N = 1007;
const int S = 5007;

const int AL = 26;

struct Node
{
	int p;
	int c;
	int g[AL];
	int nxt[AL];
	int link;
	int val;
	int sum;
	VI sons;
	
	Node(int _c, int _p)
	{
		c = _c;
		p = _p;
		fill(g, g + AL, -1);
		fill(nxt, nxt + AL, -1);
		link = -1;
		val = 0;
		sum = 0;
	}
};

struct AC
{
	vector<Node> a;
	void init(int n)
	{
		a.reserve(n);
		a.PB(Node(-1, -1));
	}
	int addStr(const string& s)
	{
		int v = 0;
		FOR(i, 0, SZ(s))
		{
			int c = s[i] - 'a';
			if (a[v].nxt[c] == -1)
			{
				a[v].nxt[c] = SZ(a);
				a.PB(Node(c, v));
			}
			v = a[v].nxt[c];
		}
		return v;
	}
	int go(int v, int c)
	{
		if (a[v].g[c] != -1)
			return a[v].g[c];
		if (a[v].nxt[c] != -1)
			a[v].g[c] = a[v].nxt[c];
		else if (v != 0)
			a[v].g[c] = go(getLink(v), c);
		else
			a[v].g[c] = 0;
		
		return a[v].g[c];
	}
	int getLink(int v)
	{
		if (a[v].link != -1)
			return a[v].link;
		if (v == 0 || a[v].p == 0)
			return 0;
		return a[v].link = go(getLink(a[v].p), a[v].c);
	}
	void dfs(int v, int sum)
	{
		sum += a[v].val;
		a[v].sum = sum;
		for (int to : a[v].sons)
		{
			dfs(to, sum);
		}
	}
};

template<typename T>
void updMax(T& a, T b)
{
	a = max(a, b);
}

db dp[S], ndp[S];

void solve()
{
	int n, m;
	string s;
	cin >> n >> m >> s;
	VI vertices(m), v(m);
	AC ac;
	ac.init(4000);
	FOR(i, 0, m)
	{
		string w;
		cin >> w >> v[i];
		vertices[i] = ac.addStr(w);
		ac.a[vertices[i]].val += v[i];
	}
	FOR(i, 1, SZ(ac.a))
	{
		ac.a[ac.getLink(i)].sons.PB(i);
	}
	ac.dfs(0, 0);
	#warning
	db l = 10.0/3, r = l;
	FOR(it, 0, 1)
	{
		db mid = (l + r) / 2;
		fill(dp, dp + SZ(ac.a), -LINF);
		fill(ndp, ndp + SZ(ac.a), -LINF);

		FOR(i, 0, n)
		{
			// ndp = dp
			int vi = ac.go(0, s[i] - 'a');
			updMax(ndp[vi], -mid);
			FOR(j, 0, SZ(ac.a))
			{
				int k = ac.go(j, s[i] - 'a');
				updMax(ndp[k], dp[j] + ac.a[k].sum - mid);
			}
			FOR(j, 0, SZ(ac.a))
				dp[j] = ndp[j];
		
		}
		if (*max_element(dp, dp + SZ(ac.a)) >= 0)
			l = mid;
		else
			r = mid;
	}
	db ans = (l + r) / 2;
	db minDiff = ans;
	int p = 0, q = 1;
	FOR(den, 1, n + 1)
	{
		LL num = round(ans * den);
		db curDiff = abs((db)num / den - ans);
		if (curDiff < minDiff)
		{
			p = num;
			q = den;
			minDiff = curDiff;
		}
	}
	cerr << ans << " " << p << " " << q << "\n";
	cout << mult(p, binpow(q, mod - 2)) << "\n";
}

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