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

i64 p[N], h[N];
int opt, m;
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;
}
void solve()
{
    cin >> s >> m;
    int n = s.length(), l = 1, r = n;
    for (int i = 0; i < n; i++)
        h[i + 1] = ((__int128_t)h[i] * base % mod + (s[i] - 'a' + 1)) % mod;
    int ans = 0;
    map<int, map<i64, int>> cnt;
    while (m--)
    {
        cin >> opt;
        if (opt == 1)
        {
            cin >> c;
            c[0] = char(((c[0] - 'a') ^ ans) % 26 + 'a');
            r++;
            h[r] = ((__int128_t)h[r - 1] * base % mod + (c[0] - 'a' + 1)) % mod;
            for (auto &[len, t] : cnt)
            {
                i64 tmp = get(r - len + 1, r);
                t[tmp]++;
            }
        }
        else if (opt == 2)
        {
            for (auto &[len, t] : cnt)
            {
                i64 tmp = get(l, l + len - 1);
                if (!--t[tmp])
                    t.erase(tmp);
            }
            l++;
        }
        else
        {
            cin >> c;
            for (char &d : c)
                d = char(((d - 'a') ^ ans) % 26 + 'a');
            ans = 0;
            int len = c.length();
            i64 tmp = cal(c);
            if (!cnt.count(len))
            {
                for (int j = l + len - 1; j <= r; j++)
                    cnt[len][get(j - len + 1, j)]++;
            }
            if (cnt[len].count(tmp))
                ans = cnt[len][tmp];
            cout << ans << '\n';
        }
    }
}
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();
}