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

const int N=10010;
double eps=1e-17;

const ll M=998244353;
ll qpow(ll a,ll b){
    ll ans=1;
    while (b){
        if(b&1)ans=ans*a%M;
        a=a*a%M;
        b>>=1;
    }
    return ans;
}

struct node{
    ll value=0;
    int next[26]={0};
    int fail;
}tree[N];
int cnt=0;

void clear(){
    for(int i=0;i<=cnt;i++){
        tree[i].value=0;
        fill(tree[i].next,tree[i].next+26,0);
        tree[i].fail=0;
    }
    cnt=0;
}

void insert(const string& s,ll v){
    int n=s.size();
    int cur=0;
    for(int i=0;i<n;i++){
        if(tree[cur].next[s[i]-'a']==0){
            tree[cur].next[s[i]-'a']=++cnt;
        }
        cur=tree[cur].next[s[i]-'a'];
    }
    tree[cur].value+=v;
}

void build(){
    queue<int> q;
    for(int i=0;i<26;i++){
        if(tree[0].next[i]!=0){
            tree[tree[0].next[i]].fail=0;
            q.push(tree[0].next[i]);
        }
    }
    while(q.size()>0){
        int x=q.front();
        q.pop();
        tree[x].value+=tree[tree[x].fail].value;
        for(int i=0;i<26;i++){
            if(tree[x].next[i]!=0){
                tree[tree[x].next[i]].fail=tree[tree[x].fail].next[i];
                q.push(tree[x].next[i]);
            }
            else tree[x].next[i]=tree[tree[x].fail].next[i];
        }
    }
}

struct Node{
    double v;
    ll a,b;  
};

int n,m;
string s;
Node p[1010][N];

bool check(double x){

    for(int i = 0; i <= n; i++){
		for(int j = 0; j <= cnt; j++){
            p[i][j].v=-1e18;
            p[i][j].a=p[i][j].b=0;
		}
	}
	
	p[0][0].v = 0;
    p[0][0].a=p[0][0].b=0;
 
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= cnt; j++){
            p[i+1][j]=p[i][j];
		}
		for(int j = 0; j <= cnt; j++){
			int ch = s[i] - 'a';
			int to = tree[j].next[ch];
            if(to==0)to=tree[j].fail;
			if(!to) continue;
			if(p[i + 1][to].v + eps < p[i][j].v + tree[to].value - x){
				p[i + 1][to].v = p[i][j].v + tree[to].value - x;
				p[i + 1][to].a = p[i][j].a + tree[to].value;
				p[i + 1][to].b = p[i][j].b + 1;
			}
		}
	}
 
	for(int i = 1; i <= cnt; i++){
		if(p[n][i].v >= 0){
			return 1;
		}
	}
	return 0;
}


void solve(){
    clear();
    cin>>n>>m;
    cin>>s;
    for(int i=0;i<m;i++){
        string t;ll v;
        cin>>t>>v;
        insert(t,v);
    }
    build();
    double l = 0, r = 2e8,ansv=0;;
 
	for(int i = 1; i <= 50; i++){
		double mid = (l + r) / 2;
		if(check(mid)){
			l = mid;
            ansv=l;
		}else{
			r = mid;
		}
	}
    check(ansv);

    for(int i = 1; i <= cnt; i++){
			if(p[n][i].v >= 0){
				int ret = p[n][i].a * qpow(p[n][i].b, M - 2) % M;
				cout << ret << "\n";
			break;
		}
	}
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=1;
    cin>>n;
    while(n--)solve();
    return 0;
}