#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int ch[4010][26],su[4010],fail[4010],cn,n,m;
char s[1010],t[1010];
double dp[4010],dp2[4010];
const double eps=1e-10;
bool chk(double e){
    dp[1]=0;
    for(int i=2;i<=cn;i++)dp[i]=-1e18;
    for(int i=1;i<=n;i++){
        int p=s[i]-'a';
        for(int j=1;j<=cn;j++)dp2[j]=dp[j];
        for(int j=1;j<=cn;j++)
            dp2[ch[j][p]]=max(dp2[ch[j][p]],dp[j]-e+su[ch[j][p]]);
        for(int j=1;j<=cn;j++)dp[j]=dp2[j];
    }
    for(int i=1;i<=cn;i++)if(dp[i]>eps)return 1;
    return 0;
}
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
void sol(){
    while(cn){
        fail[cn]=su[cn]=0;
        for(int i=0;i<26;i++)ch[cn][i]=0;
        cn--;
    }
    cn=1;
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i=1,v;i<=m;i++){
        scanf("%s%d",t+1,&v);int u=1,L=strlen(t+1);
        for(int j=1;j<=L;j++){
            int p=t[j]-'a';
            if(!ch[u][p])ch[u][p]=++cn;
            u=ch[u][p];
        }
        su[u]+=v;
    }
    queue<int>q;for(int i=0;i<26;i++)if(!ch[1][i])ch[1][i]=1;
    else fail[ch[1][i]]=1,q.push(ch[1][i]);
    while(!q.empty()){
        int u=q.front();q.pop();su[u]+=su[fail[u]];
        for(int i=0;i<26;i++)
        if(!ch[u][i])ch[u][i]=ch[fail[u]][i];
        else fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
    }
    double l=0,r=2e8;int sp=100;
    while(sp--){
        double mi=(l+r)/2;
        if(chk(mi))l=mi;
        else r=mi;
    }
    for(int i=1;i<=n;i++){
        double d=l*i;
        long long e=(long long)d;
        while(e-d>0.5)e--;
        while(d-e>0.5)e++;
        if(abs(e-d)<eps*10){
            printf("%lld\n",e%mod*qpow(i,mod-2)%mod);
            return;
        }
    }
    puts("0");
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}