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

#define ll long long

const int N = 4005;
const int M = 4005;
const double eps = 1e-12;
const double inf = 1e15;
const int mod = 998244353;

inline int qpow(int a, int b = mod - 2) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1; 
    }
    return res; 
}

char a[N], b[M];
int n, K;

vector<int> adj[M];
int fail[M];
int ch[M][26], actot;
ll val[M];

void dfs0(int u) {
    for (auto v: adj[u]) {
        val[v] += val[u];
        dfs0(v);
    }
}
void ac_build() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (ch[0][i])
            q.push(ch[0][i]), fail[ch[0][i]] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int &go = ch[u][i];
            if (go) {
                fail[go] = ch[fail[u]][i];
                q.push(go);
            } else {
                go = ch[fail[u]][i];
            }
        }
    }
    for (int i = 1; i <= actot; i++) {
        adj[fail[i]].push_back(i);
    }
    dfs0(0);
}

// f[i][j]: a[1...i], ac node j
double f[N][M], g[N][M];
inline void ckmax(double &x, double y) {
    if (x < y) x = y;
}
bool check(double ANS) {
    f[0][0] = 0, g[0][0] = -inf;
    for (int j = 1; j <= actot; j++) {
        f[0][j] = g[0][j] = -inf;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= actot; j++) {
            f[i][j] = -inf, g[i][j] = -inf;
        }
        for (int j = 0; j <= actot; j++) {
            // not choose a[i]
            ckmax(f[i][j], f[i - 1][j]);
            ckmax(g[i][j], g[i - 1][j]);
            // choose a[i]
            int trans = ch[j][a[i] - 'a'];
            ckmax(g[i][trans], max(f[i - 1][j], g[i - 1][j]) + val[trans] - ANS);
        }
//        for (int j = 0; j <= actot; j++) {
//            printf("f[%d][%d] = %.10f\n", i, j, f[i][j]);
//            printf("g[%d][%d] = %.10f\n", i, j, g[i][j]);
//        }
    }
    double t = *max_element(g[n], g[n] + actot + 1);
    return t >= -eps;
}

pair<int, int> where[N][M];
void check2(double ANS) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= actot; j++) {
            where[i][j] = {-1, -1};
        }
    }

    f[0][0] = 0, g[0][0] = -inf;
    for (int j = 1; j <= actot; j++) {
        f[0][j] = g[0][j] = -inf;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= actot; j++) {
            f[i][j] = -inf, g[i][j] = -inf;
        }
        for (int j = 0; j <= actot; j++) {
            // not choose a[i]
            ckmax(f[i][j], f[i - 1][j]);
            if (g[i][j] < g[i - 1][j])
                g[i][j] = g[i - 1][j], where[i][j] = {i - 1, j};
            // choose a[i]
            int trans = ch[j][a[i] - 'a'];
            if (g[i][trans] < f[i - 1][j] + val[trans] - ANS)
                g[i][trans] = f[i - 1][j] + val[trans] - ANS, where[i][trans] = {i - 1, -1};
            if (g[i][trans] < g[i - 1][j] + val[trans] - ANS)
                g[i][trans] = g[i - 1][j] + val[trans] - ANS, where[i][trans] = {i - 1, j};
        }
    }
    int I = n, J = max_element(g[n], g[n] + actot + 1) - g[n];
    vector<int> pos;
    while (J != -1) {
        if (where[I][J].second == -1) {
            pos.push_back(I);
            break;
        }
        if (where[I][J].second != J)
            pos.push_back(I);
        int i = where[I][J].first, j = where[I][J].second;
        I = i, J = j;
    }
    reverse(pos.begin(), pos.end());
    
//    cout << "ways = ";
//    for (auto it: pos) {
//        cout << it << ' ';
//    }
//    cout << '\n';
    
    int cur = 0;
    ll vals = 0;
    for (auto p: pos) {
        cur = ch[cur][a[p] - 'a'];
        vals += val[cur];
    }
//    printf("vals = %lld\n", vals);
     
    printf("%lld\n", vals % mod * qpow(pos.size()) % mod);
}

void sc() {
    while (actot >= 0) {
        memset(ch[actot], 0, sizeof(ch[actot]));
        fail[actot] = 0;
        val[actot] = 0;
        adj[actot].clear();
        actot--;
    }
    actot = 0;
    
    scanf("%d%d", &n, &K);
    scanf("%s", a + 1);
    while (K--) {
        scanf("%s", b + 1);
        int cur = 0;
        for (int i = 1; b[i] != '\0'; i++) {
            int &go = ch[cur][b[i] - 'a'];
            if (!go) go = ++actot;
            cur = go;
        }
        int _; scanf("%d", &_);
        val[cur] += _;
    }
    ac_build();
    
//    for (double t = -10; t <= 10; t += 1.0) {
//        printf("check(%d) = %d\n", t, check(t));
//    }
    
    double L = -2e8, R = 2e8;
    while (fabs(R - L) > eps) {
        double MID;
        if (fabs(R - L) > 1) MID = (L + R) / 2.0;
        else MID = sqrt(L * R);
        if (check(MID)) L = MID;
        else R = MID;
    }
//    printf("%.10f\n", L);
    check2(L);
}

int main() {
    int T; scanf("%d", &T);
    while (T--) sc();
    return 0;
}

/*
3
17 3
woyaoakccpcxiamen
ak 5
ccpc 6
xiamen 8
33 3
niweishenmezhengtianxunlianbuliwo
wo 3
se 1
zayin 7
39 2
programmingcontestandmewhichisimportant
me 11
gg 2
*/

/*
1
5 3
aaaaa
a 5
aa 4
aaaaa 100 
*/