#include<fstream>
#include<cstring>

#define NMAX 26

using namespace std;

ifstream f("trie.in");
ofstream g("trie.out");

struct Trie {
   int nrfii,nr_apar;
   Trie *fiu[NMAX];

   Trie()
   {
       nrfii=nr_apar=0;
       memset(fiu,0,NMAX);
   }

}*G;


char cuv[30];
void add ( void )
{
    int i=0;
    Trie *p=G;
    while(cuv[i] && p->fiu[(int)cuv[i]-'a'])
		p=p->fiu[(int)cuv[i++]-'a'];
	if(!cuv[i])
    {
         p->nr_apar++;
        return ;
    }
    while(cuv[i])
    {
        p->nrfii++;
        p->fiu[(int)cuv[i] - 'a']=new Trie;
        p=p->fiu[(int)cuv[i] - 'a'];
       i++;
    }
    p->nr_apar++;


}
void print_cuv( void )
{
    int i=0;
    Trie *p=G;
    while(cuv[i] && p->fiu[(int)cuv[i]-'a'])
        p=p->fiu[(int)cuv[i++]-'a'];
   g<<p->nr_apar<<"\n";
}
void print_pref( void )
{
    int i=0;
    Trie *p=G;
    while(cuv[i] && p->fiu[int(cuv[i])-'a'])
        p=p->fiu[(int)cuv[i++]-'a'];
    g<<i<<"\n";

}
int sw;
void erase(int i , Trie *p)
{
    if(cuv[i])
        erase(i+1, p->fiu[(int)cuv[i] - 'a']);
    else
        p->nr_apar--;
        if(sw == 1)
        {
            p->nrfii--;
            p->fiu[(int)cuv[i] - 'a'] = 0;
            sw=0;

        }
    if( ! p->nr_apar && !p->nrfii && p!=G )
    {
        delete p;
        sw=1;
    }

}


int main( void )
{

    int type;
     G=new Trie;
    while( f>>type>>cuv )
    {
         if( type == 0 )
         {

                 add();
                    continue;
                }
        if( type == 1)
                 {
                     erase(0,G);
                     continue;
                 }
            if( type == 2)
             {
              print_cuv();
              continue;

             }
          if( type == 3)
                {
                    print_pref();
                    continue;
                }





     }
}