#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxl=200000,maxt=maxl<<1,maxi=26,maxs=5000000;

int te,n,Q,m,lstans,pre;char s[maxl+5];
char t[maxs+5];int fai[maxs+5];
struct SAM{
	int p,pl,ro,son[maxt+5][maxi],fai[maxt+5],MAX[maxt+5],vis[maxt+5];
	int to[maxt+5][2],fa[maxt+5],si[maxt+5][2];bool flip[maxt+5];

	#define is_ro(p) ((p)!=to[fa[p]][0] && (p)!=to[fa[p]][1])
	#define Son(p) ((p)==to[fa[p]][1])
	inline void Pushup(int p) {si[p][1]=si[to[p][0]][1]+si[to[p][1]][1]+si[p][0]+vis[p];}
	inline void Rotate(int t){
		int p=fa[t],d=Son(t);to[p][d]=to[t][d^1];to[t][d^1]=p;
		Pushup(p);Pushup(t);if (!is_ro(p)) to[fa[p]][Son(p)]=t;
		if (to[p][d]) fa[to[p][d]]=p;fa[t]=fa[p];fa[p]=t;
	}
	inline void Addflip(int p) {swap(to[p][0],to[p][1]);flip[p]^=1;}
	inline void Pushdown(int p) {if (flip[p]) flip[p]^=1,Addflip(to[p][0]),Addflip(to[p][1]);}
	inline void Splay(int p){
		static int top,stk[maxt+5];stk[top=1]=p;
		for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
		while (top) Pushdown(stk[top--]);
		for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
			if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
	}
	inline void Access(int p){
		for (int lst=0;p;Pushup(p),lst=p,p=fa[p])
			Splay(p),si[p][0]+=si[to[p][1]][1]-si[lst][1],to[p][1]=lst;
	}
	inline void Makero(int x) {Access(x);Splay(x);Addflip(x);}
	inline void Link(int x,int y) {Makero(x);Makero(y);fa[x]=y;si[y][0]+=si[x][1];Pushup(y);}
	inline void Cut(int x,int y) {Makero(x);Access(y);Splay(y);fa[x]=to[y][0]=0;Pushup(y);}

	int newnode(){
		pl++;for (int i=0;i<maxi;i++) son[pl][i]=0;vis[pl]=0;
		to[pl][0]=to[pl][1]=fa[pl]=si[pl][0]=si[pl][1]=flip[pl]=0;
		return pl;
	}
	void clear() {pl=0;ro=newnode();p=ro;}
	void Extend(int c){
		int np=newnode();MAX[np]=MAX[p]+1;vis[np]=1;Pushup(np);
		while (p && !son[p][c]) son[p][c]=np,p=fai[p];
		if (!p) {Link(np,ro);fai[np]=ro;p=np;return;}
		int q=son[p][c];if (MAX[p]+1==MAX[q]) {Link(np,q);fai[np]=q;p=np;return;}
		int nq=newnode();MAX[nq]=MAX[p]+1;
		for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
		Cut(q,fai[q]);Link(nq,fai[q]);Link(q,nq);Link(np,nq);
		fai[nq]=fai[q];fai[q]=fai[np]=nq;
		while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
		p=np;return;
	}
}A,B;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
	T tot=0;char ch=readc(),lst='+';
	while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
	while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
	lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int reads(char *s){
	int len=0;char ch=readc();
	while (!islower(ch)) {if (ch==EOF) return EOF;ch=readc();}
	while (islower(ch)) s[++len]=ch,ch=readc();
	s[len+1]=0;return len;
}
char getlwr() {char ch=readc();while (!islower(ch)) ch=readc();return ch;}
struct fastO{
	int si;char buf[100000];
	fastO() {si=0;}
	void putc(char ch){
		if (si==100000) fwrite(buf,1,si,stdout),si=0;
		buf[si++]=ch;
	}
	~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
	int len=0,buf[100];
	if (x<0) putchar('-'),x=-x;
	do buf[len++]=x%10,x/=10; while (x);
	while (len) fo.putc(buf[--len]+48);
	fo.putc(ch);
}
inline void Insert(char ch){
	ch=((ch-'a')^lstans)%26+'a';
	s[++n]=ch;A.Extend(s[n]-'a');
}
inline void Delete() {B.Extend(s[++pre]-'a');}
int Sum(SAM &tr,char *s){
	int p=tr.ro;for (int i=1;s[i];i++) p=tr.son[p][s[i]-'a'];if (!p) return 0;
	tr.Makero(tr.ro);tr.Access(p);tr.Splay(p);
	return tr.si[p][0]+tr.vis[p];
}
int Ask(char *t,int m){
	for (int i=1;i<=m;i++) t[i]=((t[i]-'a')^lstans)%26+'a';
	int ans=Sum(A,t)-Sum(B,t);
	fai[0]=fai[1]=0;
	for (int i=2,j=0;i<=m;i++){
		while (j && t[j+1]!=t[i]) j=fai[j];
		j+=(t[j+1]==t[i]);fai[i]=j;
	}
	int L=max(pre-m+2,1),R=min(pre+m-1,n);
	for (int i=L,j=0;i<=R;i++){
		while (j && t[j+1]!=s[i]) j=fai[j];
		j+=(t[j+1]==s[i]);
		if (j==m) ans--,j=fai[j];
	}
	return ans;
}
int main(){
//	freopen("8.in","r",stdin);freopen("8.out","w",stdout);
	for (readi(te);te;te--){
		n=reads(s);A.clear();B.clear();
		for (int i=1;i<=n;i++) A.Extend(s[i]-'a');
		lstans=pre=0;
		for (readi(Q);Q;Q--){
			int tp;readi(tp);
			if (tp==1) Insert(getlwr()); else
			if (tp==2) Delete();
			else m=reads(t),lstans=Ask(t,m),writei(lstans);
		}
	}
	return 0;
}