#include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define ll long long

 using namespace std;

 const int maxn=<<;

 struct zs{int too,pre;}e[maxn];int tt,last[maxn];

 struct ask{int x,tim,timl,id;}b[maxn];

 int B[maxn];

 int ch[maxn][],fail[maxn],dl[maxn],cnt;

 int dfn[maxn],mp[maxn],TIME,L[maxn],R[maxn],TIM;

 int pos[maxn],pos1[maxn],tim1[maxn],a[maxn];

 int i,j,k,n,m;

 ll sum,an[maxn];

 bool u[maxn];

 int ra;char rx;

 inline int read(){

     rx=getchar(),ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 void dfs(int x){

     L[x]=++TIM;

     for(int i=last[x];i;i=e[i].pre)

         dfs(e[i].too);

     R[x]=TIM;//printf("    x:%d   l--r:%d %d\n",x,L[x],R[x]);

 }

 void dfs2(int x){

     dfn[x]=++TIME,mp[TIME]=x;//printf("x:%d   dfn:%d\n",x,dfn[x]);

     for(int i=;i<;i++)if(ch[x][i])

         dfs2(ch[x][i]);

     mp[++TIME]=x;

 }

 inline void insert(int a,int b){e[++tt].too=b,e[tt].pre=last[a],last[a]=tt;/*printf("%d-->%d\n",a,b);*/}

 int t[maxn],t1[maxn];

 inline void add1(int x){/*printf("  add1:%d\n",x);*/while(x<=cnt)t1[x]++,x+=x&-x;}

 inline void del1(int x){/*printf("  del1:%d\n",x);*/while(x<=cnt)t1[x]--,x+=x&-x;}

 inline int get1(int l,int r){

     int sm=;//printf("  get1:%d--%d",l,r);

     l--;while(l)sm-=t1[l],l-=l&-l;

     while(r)sm+=t1[r],r-=r&-r;/*printf(":   %d\n",sm);*/return sm;

 }

 inline int get(int x){

 //    printf("get:%d",x);

     int sm=;while(x)sm+=t[x],x-=x&-x;//printf("  %d\n",sm);

     return sm;

 }

 inline void add(int l,int r){

     if(!l)return;//printf("add:   %d--%d\n",l,r);

     sum+=get1(l,r);

     while(l<=cnt)t[l]++,l+=l&-l;

     r++;while(r<=cnt)t[r]--,r+=r&-r;

 }

 inline void del(int l,int r){

     if(!l)return;//printf("del:  %d--%d\n",l,r);

     sum-=get1(l,r);

     while(l<=cnt)t[l]--,l+=l&-l;

     r++;while(r<=cnt)t[r]++,r+=r&-r;

 }

 void getfail(){

     int l=,r=,i,p,now,j;dl[]=;

     while(l<r){

         now=dl[++l];

         for(i=;i<;i++)if(ch[now][i]){

             dl[++r]=j=ch[now][i];

             for(p=fail[now];p&&!ch[p][i];p=fail[p]);

             fail[j]=!now?:ch[p][i],insert(fail[j],j);

         }

     }

 }

 bool cmp(ask a,ask b){

     return B[a.timl]==B[b.timl]?(B[a.tim]==B[b.tim]?a.x<b.x:B[a.tim]<B[b.tim]):B[a.timl]<B[b.timl];

 }

 int main(){

     m=read();char id[],c[];int x,tm=,numb=,n=,n1=;

     for(i=;i<=m;i++){

         scanf("%s",id);

         if(id[]=='I'){

             n++,scanf("%s",c),c[]-='a',x=read();

             if(!ch[pos[x]][c[]])ch[pos[x]][c[]]=++cnt;//printf(" ..     %d %d\n",pos[x],c[0]);

             pos[n]=ch[pos[x]][c[]];//,tim[n]=tm;

         }

         if(id[]=='A'){

             n1++,scanf("%s",c),c[]-='a',x=read();

             if(!ch[pos1[x]][c[]])ch[pos1[x]][c[]]=++cnt;//,printf("      %d %d\n",pos1[x],c[0]);

             pos1[n1]=ch[pos1[x]][c[]],tim1[n1]=tm;

         }

         if(id[]=='S')

             tm++,a[tm]=pos[read()];

         if(id[]=='Q')

             b[++numb].x=read(),b[numb].tim=tm,b[numb].timl=tim1[b[numb].x]+,b[numb].id=numb;

     }

     cnt++;

     getfail();

     dfs(),dfs2();int kuai=(int)pow(tm,1.8/)+;

     for(i=;i<=tm+;i++)B[i]=(i+kuai-)/kuai;

     for(i=;i<=numb;i++)b[i].x=dfn[pos1[b[i].x]];

     sort(b+,b++numb,cmp);

     int l=,r=,pos=;L[]=R[]=,u[mp[]]=;

     for(i=;i<=numb;i++){

 //        printf("ask:  %d--%d  %d--%d  x:%d   sum:%lld\n",b[i].timl,b[i].tim,B[b[i].timl],B[b[i].tim],b[i].x,sum);

         while(l>b[i].timl)l--,add(L[a[l]],R[a[l]]);

         while(r<b[i].tim)r++,add(L[a[r]],R[a[r]]);

         while(l<b[i].timl)del(L[a[l]],R[a[l]]),l++;

         while(r>b[i].tim)del(L[a[r]],R[a[r]]),r--;//printf("sum:  %lld\n",sum);

         while(pos>b[i].x){

             if(u[mp[pos]])sum-=get(L[mp[pos]]),del1(L[mp[pos]]);else sum+=get(L[mp[pos]]),add1(L[mp[pos]]);

             u[mp[pos]]^=,pos--;

         }

         while(pos<b[i].x){

             pos++;//printf("x: %d   dfn:%d  L:%d\n",mp[pos],pos,L[mp[pos]]);

             if(u[mp[pos]])sum-=get(L[mp[pos]]),del1(L[mp[pos]]);else sum+=get(L[mp[pos]]),add1(L[mp[pos]]);

             u[mp[pos]]^=;

         }

         an[b[i].id]=sum;

     }

     for(i=;i<=numb;i++)printf("%lld\n",an[i]);

 }