#include <bits/stdc++.h>
// #include <bits/extc++.h>
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
using i64 = long long;
using namespace std;
const int N = 2e5 + 5;
// const int B = 400;
// const int M = 4e6 + 5;
const int base = 15191;
/// const int mod = 998244353;
const i64 mod = (i64)1e18 + 7;
// const double pi = acos(-1);

i64 p[N], h[N];
int n, opt, m, l, r;
string s, c;
i64 get(int l, int r)
{
    return (h[r] - (__int128_t)h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
i64 cal(string &s)
{
    i64 res = 0;
    for (char c : s)
        res = ((__int128_t)res * base % mod + (c - 'a' + 1)) % mod;
    return res;
}
struct SAM
{
    int l, r, tot, last;
    struct node
    {
        int len, link, nxt[26];
    } st[N << 1];
    int siz[N << 1];
    vector<int> adj[N << 1];
    void sam_init()
    {
        tot = 1, last = 0;
        st[0].len = 0, st[0].link = -1;
    }
    void sam_extend(char c)
    {
        int cur = tot++;
        st[cur].len = st[last].len + 1;
        siz[cur] = 1;
        int p = last;
        while (p != -1 && !st[p].nxt[c - 'a'])
        {
            st[p].nxt[c - 'a'] = cur;
            p = st[p].link;
        }
        if (p == -1)
            st[cur].link = 0;
        else
        {
            int q = st[p].nxt[c - 'a'];
            if (st[p].len + 1 == st[q].len)
                st[cur].link = q;
            else
            {
                int clo = tot++;
                st[clo].len = st[p].len + 1;
                st[clo].link = st[q].link;
                for (int j = 0; j < 26; j++)
                    st[clo].nxt[j] = st[q].nxt[j];
                while (p != -1 && st[p].nxt[c - 'a'] == q)
                {
                    st[p].nxt[c - 'a'] = clo;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clo;
            }
        }
        last = cur;
    }
    void dfs(int cur)
    {
        for (int i : adj[cur])
        {
            dfs(i);
            siz[cur] += siz[i];
        }
    }
    void rebuild(int x, int y)
    {
        for (int i = 0; i <= tot; i++)
        {
            adj[i].clear();
            memset(st[i].nxt, 0, sizeof(st[i].nxt));
            st[i].link = st[i].len = 0;
            siz[i] = 0;
        }
        l = x, r = y;
        sam_init();
        for (int i = x; i <= y; i++)
            sam_extend(s[i]);
        for (int i = 1; i <= tot; i++)
            adj[st[i].link].push_back(i);
        dfs(0);
    }
    int query(string &s)
    {
        int p = 0;
        for (char c : s)
        {
            if (!st[p].nxt[c - 'a'])
                return 0;
            p = st[p].nxt[c - 'a'];
        }
        return siz[p];
    }
} tr;
void solve()
{
    cin >> s >> m;
    n = s.length(), l = 1, r = n;
    s = ' ' + s;
    tr.l = tr.r = 0;
    for (int i = 1; i <= n; i++)
        h[i] = ((__int128_t)h[i - 1] * base % mod + (s[i] - 'a' + 1)) % mod;
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> opt;
        if (opt == 1)
        {
            cin >> c;
            c[0] = char(((c[0] - 'a') ^ ans) % 26 + 'a');
            r++;
            s.push_back(c[0]);
            h[r] = ((__int128_t)h[r - 1] * base % mod + (s[r] - 'a' + 1)) % mod;
        }
        else if (opt == 2)
            l++;
        else
        {
            cin >> c;
            for (char &d : c)
                d = char(((d - 'a') ^ ans) % 26 + 'a');
            int len = c.length();
            i64 tmp = cal(c);
            if (c.length() > tr.r - tr.l + 1)
            {
                ans = 0;
                for (int i = l + len - 1; i <= r; i++)
                    if (tmp == get(i - len + 1, i))
                        ans++;
            }
            else
            {
                ans = tr.query(c);
                for (int la = l, ra = l + len - 1; la < tr.l && ra <= r; la++, ra++)
                    if (tmp == get(la, ra))
                        ans--;
                for (int ra = tr.r + 1, la = ra - len + 1; ra <= r; la++, ra++)
                    if (tmp == get(la, ra))
                        ans++;
            }
            cout << ans << '\n';
        }
        if (i % 500 == 0)
            tr.rebuild(l, r);
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    p[0] = 1;
    for (int i = 1; i < N; i++)
        p[i] = (__int128_t)p[i - 1] * base % mod;
    int t = 1;
    cin >> t;
    // cout << fixed << setprecision(10);
    while (t--)
        solve();
}