#include <bits/stdc++.h>
#define int long long
#define double long double
#pragma GCC optimize(2)
using namespace std;
const int N = 1e5 + 10, MOD = 998244353;

int Q_pow(int a, int b){
    int ans = 1, p = a;
    while(b){
        if(b & 1) ans = (ans * p) % MOD;
        b >>= 1;
        p = (p * p) % MOD;
    }
    return ans;
}

int t;
int n, m, val[N];
string s, dict;

struct Node{
    int son[26];
    int ed, fail;
}tr[N];
int cnt = 1;
queue <int> q;

void Insert(string s, int id){
    int p = 0;
    for(auto i : s){
        int ch = i - 'a';
        if(!tr[p].son[ch]) tr[p].son[ch] = ++cnt;
        p = tr[p].son[ch];
    }
    tr[p].ed = id;
}

void Get_fail(){
    for(int i = 0; i < 26; i++){
        if(tr[1].son[i]){
            q.push(tr[1].son[i]);
        }
    }
    while(!q.empty()){
        int tp = q.front();
        q.pop();

        for(int i = 0; i < 26; i++){
            if(tr[tp].son[i]){
                tr[tr[tp].son[i]].fail = tr[tr[tp].fail].son[i];
                q.push(tr[tp].son[i]);
            }else{
                tr[tp].son[i] = tr[tr[tp].fail].son[i];
            }
        }
    }
}

double maxi;
int ans;

void Query(int st){
    int p = 0, sum = 0;
    for(int i = st; i < s.size(); i++){
        int ch = s[i] - 'a';
        p = tr[p].son[ch];
        
        int tmp = p;
        while(tmp){
            sum += val[tr[tmp].ed];
            tmp = tr[tmp].fail;
        }

        int len = i - st + 1;
        double v = 1.0 * sum / len;

        // cout << st << "+" << i << " " << sum << " ";
        // printf("%.10Lf\n", v);

        if(v > maxi){
            maxi = v;
            ans = sum * Q_pow(len, MOD - 2) % MOD;
        }
    }
}

void Reset(){
    maxi = 0, ans = 0;

    for(int i = 1; i <= cnt; i++){
        memset(tr[i].son, 0, sizeof(tr[i].son));
        tr[i].ed = tr[i].fail = 0;
    }
    cnt = 1;
}

signed main(){
    // freopen("1.in", "r", stdin);

    cin >> t;
    while(t--){
        cin >> n >> m >> s;
        for(int i = 1; i <= m; i++){
            cin >> dict >> val[i];
            Insert(dict, i);
        }
        Get_fail();

        for(int i = 0; i < s.size(); i++){
            Query(i);
        }
        cout << ans << "\n";

        Reset();
    }
}