#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 = 191;
/// const int mod = 998244353;
const i64 mod = (i64)1e18 + 7;
// const double pi = acos(-1);

i64 p[N], h[N];
int opt, m;
gp_hash_table<i64, int> cnt[100];
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;
    set<int> occur;
    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 : occur)
            {
                i64 tmp = get(r - len + 1, r);
                cnt[len][tmp]++;
            }
        }
        else if (opt == 2)
        {
            for (auto &len : occur)
            {
                i64 tmp = get(l, l + len - 1);
                if (!--cnt[len][tmp])
                    cnt[len].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 (len >= 100)
            {
                for (int j = l + len - 1; j <= r; j++)
                    if (get(j - len + 1, j) == tmp)
                        ans++;
            }
            else
            {
                if (!occur.count(len))
                {
                    occur.insert(len);
                    for (int j = l + len - 1; j <= r; j++)
                        cnt[len][get(j - len + 1, j)]++;
                }
                ans = cnt[len][tmp];
                if (!ans)
                    cnt[len].erase(tmp);
            }
            cout << ans << '\n';
        }
    }
    for (int i : occur)
        cnt[i].clear();
}
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();
}