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

const int N = 4010;
const int A = 26;

int go[N][A], trie[N][A], suf[N], par[N], letter[N];
int cnt[N];
int sz = 1;

void add(string s, int val) {
    int u = 1;
    for (auto c : s) {
        int x = c - 'a';
        if (!trie[u][x]) {
            trie[u][x] = ++sz;
            par[sz] = u;
            letter[sz] = x;
        }
        u = trie[u][x];
    }
    cnt[u] += val;
}
void build() {
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int u = q.front();
        q.pop();
        if (u == 1 || par[u] == 1) suf[u] = 1;
        else suf[u] = go[suf[par[u]]][letter[u]];
        for (int i = 0; i < A; ++i) {
            if (trie[u][i]) go[u][i] = trie[u][i];
            else go[u][i] = go[suf[u]][i];
            go[u][i] = max(go[u][i], 1);
        }
        for (int i = 0; i < A; ++i) {
            if (trie[u][i]) q.push(trie[u][i]);
        }
        cnt[u] += cnt[suf[u]];
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;
        for (int i = 0; i < m; ++i) {
            string t;
            cin >> t;
            int x;
            cin >> x;
            add(t, x);
        }
        build();
        auto check = [&](double x) -> bool {
            vector<double> dp(sz + 1, -1e9);
            vector<double> nw(sz + 1, -1e9);
//            cout << x << endl;
            for (auto i : s) {
                nw[go[1][i - 'a']] = max(nw[go[1][i - 'a']], cnt[go[1][i - 'a']] - x);
                for (int j = 1; j <= sz; ++j) {
                    int k = go[j][i - 'a'];
                    nw[k] = max(nw[k], dp[j] + cnt[k] - x);
                }
//                cout << i << endl;
//                for (int j = 1; j <= sz; ++j) cout << nw[j] << ' ';
//                cout << endl;
                dp = nw;
            }
            return *max_element(dp.begin(), dp.end()) >= 0;
        };
        double l = 0, r = 2e8;
        for (int iter = 0; iter < 50; ++iter) {
            double mid = (l + r) / 2;
            if (check(mid)) l = mid;
            else r = mid;
        }
//        cout << l << ' ' << r << endl;
        for (int i = 1; i <= n; ++i) {
            long long x = l * i;
            long long y = i;
            while (x - l * y > 0.1) --x;
            while (x - l * y < -0.1) ++x;
//            cout << i << ' ' << x << ' ' << y << ' ' << abs(x - l * y) << endl;
            if (abs(x - l * y) <= 1e-3) {
                int mod = 998244353;
                int b = mod - 2;
                int res = 1;
                for (; b; b >>= 1, y = 1ll * y * y % mod) if (b & 1) res = 1ll * res * y % mod;
                cout << 1ll * res * x % mod << '\n';
                break;
            }
        }
        for (int i = 1; i <= sz; ++i) {
            cnt[i] = suf[i] = letter[i] = par[i] = 0;
            for (int j = 0; j < A; ++j) trie[i][j] = go[i][j] = 0;
        }
        sz = 1;
    }
}