#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define drp(i,j,k) for(int i=j;i>=(k);--i)
#define isdigit(ch) (ch>=48&&ch<=57)
#define mp std::make_pair
#define mod 998244353
#define MAXN 1000005
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
inline int read(){
	int x=0;
	bool sgn=true;
	char ch=getchar();
	while(!isdigit(ch)) sgn^=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return sgn?x:-x;
}
inline ll readll(){
	ll x=0;
	bool sgn=true;
	char ch=getchar();
	while(!isdigit(ch)) sgn^=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return sgn?x:-x;
}
template <typename tp> inline tp min(tp x,tp y){return x<y?x:y;}
template <typename tp> inline tp max(tp x,tp y){return x>y?x:y;}
template <typename tp> inline bool chkmin(tp &x,tp y){return x>y&&(x=y,true);}
template <typename tp> inline bool chkmax(tp &x,tp y){return x<y&&(x=y,true);}
int task,n,m;
char a[MAXN];
ld f[1005][4005];
namespace acam{
	int pos;
	std::queue<int> q;
	struct node{
		int ch[26];
		int fail;
		ll sum;
	}tree[MAXN];
	inline void init(){
		std::queue<int>().swap(q);
		while(pos){
			memset(tree[pos].ch,0,sizeof(tree[pos].ch));
			tree[pos].fail=0,tree[pos].sum=0,--pos;
		}
		pos=1;
	}
	inline void ins(const std::string &s,ll val){
		int u=1;
		for(auto x:s){
			int id=x-'a';
			if(!tree[u].ch[id]) tree[u].ch[id]=++pos;
			u=tree[u].ch[id];
		}
		tree[u].sum+=val;
	}
	inline void bfs(){
		q.push(1);
		rep(i,0,25) tree[0].ch[i]=1;
		while(!q.empty()){
			int u=q.front();
			tree[u].sum+=tree[tree[u].fail].sum,q.pop();
			rep(i,0,25){
				int v=tree[u].ch[i],fail=tree[u].fail;
				if(!v) tree[u].ch[i]=tree[fail].ch[i];
				else tree[v].fail=tree[fail].ch[i],q.push(v);
			}
		}
	}
	inline int trans(int x,char y){
		return tree[x].ch[y-'a'];
	}
	inline ll getval(int x){
		return tree[x].sum;
	}
}
inline ll pw(int x,int y){
	ll base=x,ret=1;
	for(;y;y>>=1,(base*=base)%=mod) if(y&1) (ret*=base)%=mod;
	return ret;
}
inline bool chk(ld x){
	rep(i,0,n) rep(j,0,acam::pos) f[i][j]=-1e18;
	f[0][1]=0;
	rep(i,0,n-1) rep(j,1,acam::pos){
		if(f[i][j]==-1e18) continue;
		int k=acam::trans(j,a[i+1]);
		chkmax(f[i+1][j],f[i][j]);
		chkmax(f[i+1][k],f[i][j]+acam::getval(k)-x);
	}
	return *std::max_element(f[n]+1,f[n]+acam::pos+1)>0;
}
inline ll solve(){
	ld l=0,r=1e9;
	while(r-l>1e-9){
		ld mid=(l+r)/2;
		if(chk(mid)) l=mid;
		else r=mid;
	}
	int x=0,y=1;
	ld rst=r-floorl(r);
	rep(i,1,n) rep(j,1,i-1){
		if((ld)j/i>rst+1e-9) continue;
		if(j*y>i*x) x=j,y=i;
	}
	return (((ll)r)+x*pw(y,mod-2))%mod;
}
int main(){
	drp(task,read(),1){
		n=read(),m=read(),scanf("%s",a+1);
		acam::init();
		rep(i,1,m){
			std::string s;
			ll val=0;
			std::cin>>s,val=read();
			acam::ins(s,val);
		}
		acam::bfs();
		printf("%lld\n",solve());
	}
}