#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define p pair<int,string>

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

struct trie {
    int word;
    int prefix;
    trie *edge[26];
   trie () {   word = prefix = 0;
    memset(edge , 0 , sizeof(edge));}
};

trie *T = new trie;
string s;
p num;

void addword(trie *nod, string wd, int r)
{
    if (r == wd.length()) {nod->word += 1; return;}

    if (nod->edge[wd[r] - 'a' ] == 0 )
    {
        nod ->edge[wd[r] - 'a' ] = new trie;
        nod->prefix++;
    }
   addword(nod->edge[wd[r] - 'a'],wd,r+1);
}

int delword(trie *nod, string wd, int r)
{
    if (r == wd.length() ) nod->word -=1;
      else
    if (delword(nod->edge[wd[r] - 'a'],wd,r+1))
    {
        nod->edge[wd[r] - 'a'] = 0;
        nod->prefix--;
    }
    if (nod->word == 0 && nod->prefix == 0 && nod != T)
    {        delete nod; return 1;   }
    return 0;
}

int nword(trie *nod,string wd, int r)
{
    if (r == wd.length()) { return nod->word; }

    if (nod->edge[wd[r] - 'a'] )
       return nword(nod->edge[wd[r] - 'a'],wd,r+1);
    return 0;
}

int npref(trie *nod,string wd , int r , int k)
{
    if ((r == wd.length() )|| (nod->edge[wd[r] - 'a'] == 0))
          return k;
    return npref(nod->edge[wd[r] - 'a'],wd,r+1,k+1);
}

int main()
{

    while (!f.eof())
    {
            getline(f,s);
          num.first = s[0] - '0';
          s.erase(0,2);
          num.second = s;
          cout << num.first << " " << num.second << "\n";

         switch (num.first)
         {
         case 0 : addword(T,num.second,0); break;
         case 1 : delword(T,num.second,0); break;
         case 2 : g << (nword(T,num.second,0)) << "\n"; break;
         case 3 : g << (npref(T,num.second,0,0)) << "\n"; break;
         }
    }
    return 0;
}