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

#define ll long long

const int N = 2005;
const int M = 4005;
const ll inf = 1e18;
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);
}

struct Foo {
    ll a, b; 
};
 
// f[i][j]: a[1...i], ac node j
ll f[N][M], g[N][M];
inline void ckmax(ll &x, ll y) {
    if (x < y) x = y;
}
inline ll check(Foo cur) {
    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] * cur.b - cur.a);
        }
//        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]);
//        }
    }
    ll t = *max_element(g[n], g[n] + actot + 1);
    return t; 
}

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));
//    }
    
    Foo L = {0, 1}, R = {1, 0}, ans; 
    while (1) {
        Foo MID = {L.a + R.a, L.b + R.b};
        ll p = check(MID);
//        printf("check %lld/%lld, p = %lld\n", mid.a, mid.b, p); 
        if (p == 0) {
            ans = MID;
            break; 
        } 
        if (p > 0) {
            ll l = 1, r = (1000000000 - L.a) / R.a;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                Foo go = {L.a + mid * R.a, L.b + mid * R.b};
                if (check(go) >= 0) l = mid;
                else r = mid - 1; 
            } 
            L = {L.a + l * R.a, L.b + l * R.b}; 
        } else {
            ll l = 1, r = (1000000000 - R.a) / L.a;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                Foo go = {R.a + mid * L.a, R.b + mid * L.b};
                if (check(go) < 0) l = mid;
                else r = mid - 1;
            } 
            R = {R.a + l * L.a, R.b + l * L.b};
        } 
    }
//    printf("ans = (%lld, %lld)\n", ans.a, ans.b); 
    printf("%lld\n", ans.a % mod * qpow(ans.b) % mod);
}

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 
*/