#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;
       for(int i=0;i < 25 ; ++i )
        fiu[i]=0;
   }
 
}*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'];
 if(!cuv[i] )
   g<<p->nr_apar<<"\n";
   else
    g<<"0\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;
                }
    }
}