#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1010;
const int maxp = 4010;
const int mod  = 998244353;
const double eps = 1e-9;

int pw(int x,int k)
{
	int re=1;
	for(;k;k>>=1,x=(ll)x*x%mod) if(k&1)
		re=(ll)re*x%mod;
	return re;
}
int inv(int x){ return pw(x,mod-2); }

struct Trie
{
	int rt,tot;
	int son[maxp][26],sum[maxp],fail[maxp];
	int newnode()
	{
		++tot;
		memset(son[tot],0,sizeof son[tot]);
		sum[tot]=fail[tot]=0;
		return tot;
	}
	void init()
	{
		rt=tot=0;
		rt=newnode();
	}
	void insert(string ss,const int val)
	{
		int x=rt;
		for(auto c:ss)
		{
			int w=c-'a';
			if(!son[x][w]) son[x][w]=newnode();
			x=son[x][w];
		}
		sum[x]+=val;
	}
	void build()
	{
		queue<int>q;
		q.push(rt); fail[rt]=0;
		while(!q.empty())
		{
			const int x=q.front(); q.pop();
			int fl=fail[x];
			sum[x]+=sum[fl];
			for(int w=0;w<26;w++)
			{
				int &y=son[x][w];
				if(y)
				{
					if(x!=rt) fail[y]=son[fl][w];
					else fail[y]=x;
					q.push(y);
				}
				else
				{
					if(x!=rt) y=son[fl][w];
					else y=rt;
				}
			}
		}
	}
}tr;

int n,m;
string S;

int tf[maxn][maxp],tn;
double f[maxn][maxp];
int pf[maxn][maxp];
inline void upd(const int i,const int j,const double F,const int pj)
{
	if(tf[i][j]!=tn) 
	{
		tf[i][j]=tn, f[i][j]=F;
		pf[i][j]=pj;
	}
	else if(f[i][j]<F) f[i][j]=F, pf[i][j]=pj;
}
int check(const double mid)
{
	f[0][tr.rt]=0;
	tf[0][tr.rt]=tn;
	for(int i=0;i<=n;i++)
	{
		for(int j=1;j<=tr.tot;j++) if(tf[i][j]==tn)
		{
			if(i && f[i][j]>eps) return 1;
			if(i<n)
			{
				upd(i+1,j,f[i][j],-j);
				int w=S[i+1]-'a';
				int nj= tr.son[j][w];
				upd(i+1,nj,f[i][j]-mid+tr.sum[nj],j);
			}
		}
	}
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>m;
		cin>>S; S=' '+S;
		
		tr.init();
		double l=0,r=0;
		for(int i=1;i<=m;i++)
		{
			string ss; cin>>ss;
			int c; cin>>c;
			tr.insert(ss,c);
			r+=c;
		}
		tr.build();
		
		tn=0;
		for(int ti=1;ti<=50;ti++)
		{
			double mid=(l+r)/2;
			++tn;
			if(check(mid)) l=mid;
			else r=mid;
		}
		++tn; check(l);
		
		int edi=0,edj;
		for(int i=1;i<=n && edi==0;i++) for(int j=1;j<=tr.tot;j++) if(tf[i][j]==tn)
		{
			if(f[i][j]>eps)
			{
				edi=i,edj=j;
				break;
			}
		}
		ll ansp=0,ansq=0;
		while(edi)
		{
			ansp+=(pf[edi][edj]>0)*tr.sum[edj];
			ansq+=(pf[edi][edj]>0);
			edj=abs( pf[edi][edj] );
			edi--;
		}
	//	cerr<<fixed<<setprecision(12)<<l<<' '<<r<<'\n';
	//	cerr<<ansp<<'/'<<ansq<<'\n';
		cout<<ansp%mod*inv(ansq)%mod<<'\n';
	}
	
	return 0;
}