#include <bits/stdc++.h>

using namespace std;

const int N = 1005, M = 4005, P = 998244353;

int tot, ch[26][M], fail[M], sum[M];
long double f[M], g[M];
vector<int> T[M];

void dfs(int x) {
    for (auto v : T[x]) sum[v] += sum[x], dfs(v);
}

signed main() {
    int te; scanf("%d", &te);
    while (te--) {
        int n, m; scanf("%d%d", &n, &m);
        string S; cin >> S;
        S = ' ' + S;
        for (int i = 0; i <= tot; ++i) {
            fail[i] = sum[i] = 0;
            for (int j = 0; j < 26; ++j) ch[j][i] = 0;
        }
        tot = 0;
        for (int i = 1; i <= m; ++i) {
            string str;
            cin >> str;
            int now = 0;
            for (auto c : str) {
                c -= 'a';
                if (!ch[c][now]) ch[c][now] = ++tot;
                now = ch[c][now];
            }
            int val; scanf("%d", &val);
            sum[now] += val;
        }
        queue<int> Q;
        for (int i = 0; i < 26; ++i) {
            if (ch[i][0]) Q.push(ch[i][0]);
        }
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i = 0; i < 26; ++i) {
                if (ch[i][x]) fail[ch[i][x]] = ch[i][fail[x]], Q.push(ch[i][x]);
                else ch[i][x] = ch[i][fail[x]];
            }
        }
        for (int i = 0; i <= tot; ++i) T[i].clear();
        for (int i = 1; i <= tot; ++i) T[fail[i]].push_back(i);
        dfs(0);
        long double L = 0, R = 1e8, res = 0;
        while (fabs(L - R) > 1e-10) {
            long double mid = (L + R) / 2;
            for (int j = 0; j <= tot; ++j) f[j] = -1e18;
            f[0] = 0;
            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j <= tot; ++j) g[j] = f[j];
                for (int j = 0; j <= tot; ++j) {
                    int k = S[i] - 'a';
                    f[ch[k][j]] = max(f[ch[k][j]], g[j] + sum[ch[k][j]] - mid);
                }
            }
            int flg = 0;
            for (int j = 0; j <= tot; ++j) {
                flg |= (f[j] > 1e-10);
            }
            if (flg) {
                res = mid, L = mid;
            } else {
                R = mid;
            }
        }
        for (int i = 1; i <= n; ++i) {
            long double v = res * i;
            if ((int)floor(v + 1e-9) != (int)floor(v - 1e-9)) {
                int res = (int)floor(v + 1e-9), x = i, y = P - 2;
                while (y) {
                    if (y & 1) res = 1ll * res * x % P;
                    x = 1ll * x * x % P;
                    y >>= 1;
                }
                printf("%d\n", res);
                break;
            }
        }
    }
    return 0;
}