#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+5;
class AC_
{
public: 
    int tr[N][26], cnt, fail[N];
    ll e[N];
    vector<int> G[N];
public:
    void init()
    {
        for(int i=0; i<=cnt; ++i)
        {
            fail[i]=0;
            memset(tr[i], 0, sizeof tr[i]);
            e[i]=0;
            G[i].clear();
        }
        cnt=0;
    }
    void insert(string s, ll v)
    {
        int p=0;
        for(int i=0; i<s.size(); i++)
        {
            int k=s[i]-'a';
            if(!tr[p][k]) tr[p][k]=++cnt;
            p=tr[p][k];
        }
        e[p]+=v;
    }
    void dfs(int x, ll v)
    {
        for(auto y:G[x]) dfs(y, v+e[x]);
        e[x]+=v;
    }
    void build()
    {
        queue<int> q;
        memset(fail, 0, sizeof(fail));
        for (int i=0; i<26; ++i) if(tr[0][i]) q.push(tr[0][i]);
        while(!q.empty())
        {
            int k=q.front(); q.pop();
            for(int i=0; i<26; ++i)
            {
                if(tr[k][i]) fail[tr[k][i]] = tr[fail[k]][i], q.push(tr[k][i]);
                else tr[k][i] = tr[fail[k]][i];
            }
        }
        for(int i=1; i<=cnt; ++i) G[fail[i]].push_back(i);
        dfs(0, 0);
    }
}ac;

int n, m;
string s;
ll dp[2][N];
const ll INF=1e18;
bool chk(ll mid, ll _ = 1) // ans>mid?
{
    dp[0][0]=0;
    for(int i=1;i<=ac.cnt;++i) dp[0][i]=-INF;
    for(int j=0,p=1;j<n;++j,p=1-p)
    {
        int c=s[j]-'a';
        for(int i=0;i<=ac.cnt;++i) dp[p][i]=dp[1-p][i];
        for(int i=0;i<=ac.cnt;++i) 
        {
            if(dp[1-p][i]!=-INF) dp[p][ac.tr[i][c]]=max(dp[p][ac.tr[i][c]], dp[1-p][i]+_*ac.e[ac.tr[i][c]]-mid);
        }
    }
    ll mx=0;
    for(int i=0;i<=ac.cnt;++i) mx=max(mx, dp[n&1][i]);
    return mx>0;
}

tuple<double, int, int> val[1000005]; int tot=0;
const int Mod=998244353;
ll fpow(ll x, ll y)
{
    ll r=1;
    for(;y;y>>=1,x=x*x%Mod) if(y&1) r=r*x%Mod;
    return r;
}

void solve()
{
    std::cin >> n >> m;
    std::cin >> s;
    ac.init();
    for(int i = 1; i <= m; ++i)
    {
        string t; ll v;
        std::cin >> t >> v;
        ac.insert(t.c_str(), v);
    }
    ll ans=-1, l=0, r=1ll*n*n*100000;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(chk(mid, 1)) ans=mid, l=mid+1;
        else r=mid-1;
    }
    if(ans==-1) 
    {
        cout << "0\n";
        return ;
    }
    tot = 0;
    for(int i=1;i<=n;++i)for(int j=1;j<=i;++j) if(gcd(i,j)==1) val[++tot]={(double)j/i, j, i};
    sort(val+1, val+tot+1);
    l=1, r=tot-1; int anss=0;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        auto [x,y,z]=val[mid];
        if(chk(y+z*ans, z)) anss=mid, l=mid+1;
        else r=mid-1;
    }
    ++anss;
    auto [x,y,z]=val[anss];
    assert(z <= n);
    ans=(ans%Mod*z%Mod+y)%Mod;
    ans=(ans*fpow(z%Mod, Mod-2))%Mod;
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    // for(int i=1;i<=1000;++i)for(int j=1;j<=i;++j) if(gcd(i,j)==1) val[++tot]={(double)j/i, j, i};
    // sort(val+1, val+tot+1);
    
    int T;
    std::cin >> T;
    while(T--) solve();
}