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

const int N=1000010;
double eps=1e-10;

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[2][N];

ll ans=0;

bool check(double x){
    int cur=0;
    for(int i=0;i<=cnt;i++)p[cur][i]={-1e18,0,0};
    p[cur][0]={0,0,0};
    for(int i=0;i<s.size();i++){
        for(int j=0;j<=cnt;j++)p[cur^1][j]=p[cur][j];
        for(int j=0;j<=cnt;j++){
            int nxtj;
            if(tree[j].next[s[i]-'a']>0)nxtj=tree[j].next[s[i]-'a'];
            else nxtj=tree[j].fail;
            if(p[cur^1][nxtj].v+eps<p[cur][j].v+tree[nxtj].value-x){
                p[cur^1][nxtj].a=p[cur][j].a+tree[nxtj].value;
                p[cur^1][nxtj].b=p[cur][j].b+1;
                p[cur^1][nxtj].v=p[cur][j].v+tree[nxtj].value-x;
            }
        }
        cur^=1;
    }
    for(int i=0;i<=cnt;i++){
        if(p[cur][i].v>=-1e-8&&p[cur][i].b>0){
            ans=p[cur][i].a*qpow(p[cur][i].b,M-2)%M;
            // cout<<p[cur][i].v<<" "<<p[cur][i].a<<" "<<p[cur][i].b<<"\n";
            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();
    ans=0;
    double l=0,r=2e8;
    while(r-l>eps){
        double m=(r+l)/2.0;
        if(check(m))l=m;
        else r=m;
    }
    cout<<ans<<"\n";
}

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