#include<fstream>
#include<vector>
#include<cstring>
using namespace std;

struct cell
{
    int frecv;
    bool sf;
};

ifstream fin("trie.in");
ofstream fout("trie.out");

const int oo=1<<30;

char s[30];
cell mat[25][30][30];

inline void STARE(char *t,bool ok)
{
    int i,len;
    len=strlen(t+1);
    t[0]='a';
    for (i=0;i<len;i++)
        {
            if (!ok)
                mat[i][s[i]-'a'+1][s[i+1]-'a'+1].frecv++;
            else mat[i][s[i]-'a'+1][s[i+1]-'a'+1].frecv--;
            if (i==len-1)
                {
                    if (!ok)
                        mat[i][s[i]-'a'+1][s[i+1]-'a'+1].sf=1;
                    else mat[i][s[i]-'a'+1][s[i+1]-'a'+1].sf=0;
                }
        }
}

inline void COUNT(char *t)
{
    int i,len,sol=oo;
    len=strlen(t+1);
    t[0]='a';
    for (i=0;i<len;i++)
        sol=min(sol,mat[i][s[i]-'a'+1][s[i+1]-'a'+1].frecv);
    if (i==len)
        {
            i--;
            if (mat[i][s[i]-'a'+1][s[i+1]-'a'+1].sf==0) fout<<"0\n";
            else fout<<sol<<"\n";
        }
}

inline void PREFIX(char *t)
{
    int i,len,nr=0;
    len=strlen(t+1);
    t[0]='a';
    i=0;
    while (mat[i][s[i]-'a'+1][s[i+1]-'a'+1].frecv) i++,nr++;
    fout<<nr<<"\n";
}

inline void SOLVE()
{
    int ok;
    while (fin>>ok)
        {
           fin>>(s+1);
           if (!ok) STARE(s,0);
           if (ok==1) STARE(s,1);
           if (ok==2) COUNT(s);
           if (ok==3) PREFIX(s);
        }
}

int main()
{
    SOLVE();
    return 0;
}