#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef double db;
const int N = 1010,M = 4010,K = 26,mod = 998244353;
const db eps = 1e-6;
int qpow(int a,int n){
    int res = 1; a%=mod;
    while(n){
        if(n&1)res = 1ll*res*a%mod;
        n>>=1; a = 1ll*a*a%mod;
    }
    return res;
}
int qinv(int a){return qpow(a,mod-2);}
//
int T,n,m; string s;

int ch[M][K],sum[M],fail[M],tot;

struct Info{
    db w; int cnt;
    Info(db vw = -1e18,int vc = 1e9){w = vw,cnt = vc;}
}; Info Z;
bool operator>(Info x,Info y){
    if(fabs(x.w-y.w) < eps)return x.cnt < y.cnt;
    else return x.w > y.w;
}
bool operator==(Info x,Info y){
    return fabs(x.w-y.w) < eps && x.cnt == y.cnt;
}

void build(){
    queue<int> qu;
    for(int i=0;i<K;i++)if(ch[0][i])qu.push(ch[0][i]);
    while(qu.size()){
        int u = qu.front(); qu.pop(); sum[u] += sum[fail[u]];
        for(int i=0;i<K;i++){
            if(ch[u][i])fail[ch[u][i]] = ch[fail[u]][i],qu.push(ch[u][i]);
            else ch[u][i] = ch[fail[u]][i];
        }
    }
}

Info dp[N][M];
Info calc(db w){
    for(int i=0;i<=n;i++)for(int j=0;j<=tot;j++)dp[i][j] = Z;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=tot;j++){
            Info pre = dp[i-1][j]; if(pre == Z)continue;
            if(pre > dp[i][j])dp[i][j] = pre;
            int k = ch[j][s[i]-'a']; 
            pre.w += sum[k] + w; pre.cnt++;
            if(pre > dp[i][k])dp[i][k] = pre;
        }
        int k = ch[0][s[i]-'a']; Info now(sum[k]+w,1);
        if(now > dp[i][k])dp[i][k] = now;
    }
    Info res = Z;
    for(int j=0;j<=tot;j++)if(dp[n][j] > res)res = dp[n][j];
    return res;
}

void solve(){
    memset(ch,0,sizeof ch); memset(fail,0,sizeof fail); memset(sum,0,sizeof sum); tot = 0;

    cin>>n>>m>>s; s=" "+s;
    for(int i=1;i<=m;i++){
        string tmp; cin>>tmp; int w; cin>>w;
        int u = 0,len = tmp.length();
        for(int j=0;j<len;j++){
            int& v = ch[u][tmp[j]-'a'];
            if(!v)v = ++tot; u = v;
        }
        sum[u] += w;
    }
    build();
    //
    db L = 0,R = 1e11; int len = 0;
    while(R-L > eps){
        db mid = (L+R)/2;
        Info rev = calc(-mid);
        if(rev.w >= 0){
            len = rev.cnt; L = mid;
        }else{
            R = mid;
        }
    }
    //
    ll vL = 1,vR = 1e11,vres = 0; 
    while(vL<=vR){
        ll mid = (vL+vR)>>1; 
        db w = 1.00*mid/len;
        Info rev = calc(-w);
        if(rev.w >= -eps){
            vres = mid,vL = mid+1;
        }else{
            vR = mid-1;
        }
    }
    //
    vres %= mod;
    int ans = 1ll*vres*qinv(len)%mod; cout<<ans<<"\n";
}

int main(){
    cin>>T;
    while(T--)solve();

    return 0;
}