N14612.cpp

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

#define int long long
#define pb push_back
#define lowbit(x) ((x) & (-x))
const int N = 3e6+10;

int tr[N][26], idx;
bool unlocked[N];
int fail[N], sum[N], dfn[N], sz[N], ts;
vector<int> g[N];

int querysum(int p) {
    int res = 0;
    for (; p; p -= lowbit(p)) res += sum[p];
    return res;
}

void add(int p, int k) {
    for (; p <= ts; p += lowbit(p)) sum[p] += k;
}

void init() {
    for (int i = 1; i <= ts; i++) {
        dfn[i] = 0;
        sum[i] = 0;
    }
    ts = 0;

    for (int i = 0; i <= idx; i++) {
        fail[i] = 0;
        sz[i] = 0;
        unlocked[i] = false;
        vector<int>().swap(g[i]);

        for (int j = 0; j < 26; j++) {
            tr[i][j] = 0;
        }
    }
    idx = 0;
}

void insert(const string& s) {
    int u = 0;
    for (char c: s) {
        int p = c - 'a';
        if (!tr[u][p]) tr[u][p] = ++idx;
        u = tr[u][p];
    }
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]);
    while (q.size()) {
        int fa = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int& u = tr[fa][i];
            if (!u) u = tr[fail[fa]][i];
            else {
                fail[u] = tr[fail[fa]][i];
                q.push(u);
            }
        }
    }

    for (int i = 1; i <= idx; i++) g[fail[i]].pb(i);
}

void dfs(int u) {
    dfn[u] = ++ts;
    sz[u] = 1;
    for (int to: g[u]) {
        dfs(to);
        sz[u] += sz[to];
    }
}

void unlock(const string& s) {
    int u = 0;
    for (char c: s) {
        int p = c - 'a';
        u = tr[u][p];
        if (!unlocked[u]) {
            unlocked[u] = true;
        }
    }
    add(dfn[u], 1);
    add(dfn[u] + sz[u], -1);
}

int query(const string& t) {
    int j = 0, res = 0;
    for (char c: t) {
        int p = c - 'a';
        while (j && (!tr[j][p] || !unlocked[tr[j][p]])) j = fail[j];
        if (tr[j][p] && unlocked[tr[j][p]]) j = tr[j][p];
        res += querysum(dfn[j]);
    }
    return res;
}

struct Query {
    string s;
    int m;
};

void solve() {
    init();
    int n, m;
    cin >> n >> m;
    vector<string> strs;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        strs.pb(s);
    }
    vector<Query> qrys;
    for (int i = 1; i <= m; i++) {
        int op;
        string s;
        cin >> op >> s;
        if (op == 1) strs.pb(s);
        else qrys.pb({s, (int)strs.size() - 1});
    }

    for (string& s: strs) insert(s);
    build();
    dfs(0);

    int j = 0;
    for (const auto& [s, m]: qrys) {
        while (j <= m) unlock(strs[j++]);
        cout << query(s) << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}