#include <fstream>

using namespace std;

int t;
char s[30];

struct trie
{
    int nrc,nrp;
    trie *nod[26];
    trie()
    {
        nrc = nrp = 0;
        for(int i = 0; i <= 26; ++i)
            nod[i] = 0;
    }
}*root;

void add(trie *rad, char *s)
{
    if (*s == 0)
    {
        rad->nrc++;
        return;
    }

    if (rad->nod[*s-'a'] == NULL )
    {
        rad->nod[*s-'a'] = new trie;
        rad -> nrp ++;
    }

    add(rad->nod[*s-'a'],s+1);
}

bool sterge(trie *&rad, char *s)
{
  if (*s == 0)
  {
      rad->nrc--;
      if (rad -> nrp ==0 && rad -> nrc ==0 && rad != root)
      {
          //delete rad;
          rad = NULL;
          return 1;
      }
      return 0;
  }

  if (sterge(rad->nod[*s-'a'],s+1))
  {
    rad->nrp --;
    if (rad -> nrp == 0 && rad -> nrc == 0 && rad != root)
    {
        //delete rad;
        rad = NULL;
        return 1;
    }
    return 0;
  }

}

int apcuv(trie *rad, char *s)
{
    if(*s == 0) return rad->nrc;
    if (rad->nod[*s-'a'] !=NULL ) return apcuv(rad->nod[*s-'a'],s+1);
        else return 0;
}

int prefix(trie *rad, char *s)
{
    if(*s == 0) return 0;
        if(rad -> nod[*s - 'a'] != NULL) return 1 + prefix(rad->nod[*s-'a'],s+1);
            else return 0;
}

int main()
{
    ifstream f("trie.in");
    ofstream g("trie.out");
    root = new trie;
    while(f>>t>>s)
    {
        if (t == 0)
        {
            add(root,s);
        }
        if (t == 1)
        {
            sterge(root,s);
        }
        if (t == 2)
        {
            g<<apcuv(root,s)<<"\n";
        }
        if (t == 3)
        {
            g<<prefix(root,s)<<"\n";
        }
    }
    return 0;
}