#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>

using namespace std;

ifstream fi("trie.in");
ofstream fo("trie.out");

int t,w,l;
string ss;

struct trie{
    int k,nrch;
    trie *child[26];

    trie()
    {
        k=nrch=0;
        memset(child,0,sizeof(child));
    }

};

trie *T=new trie;

void push(trie *nod, int poz)
{
    if(poz==l)
    {
        nod->k++;
        return;
    }

    if(nod->child[ss[poz]-'a']==NULL)
    {
        nod->child[ss[poz]-'a']=new trie;
        nod->nrch++;
    }

    push(nod->child[ss[poz]-'a'], poz+1);

}

int pop(trie *nod, int poz)
{
    if(poz==l)
        nod->k--;
    else if(pop(nod->child[ss[poz]-'a'], poz+1))
    {
        nod->nrch--;
        nod->child[ss[poz]-'a']=NULL;
    }

    if(nod->nrch==0 && nod->k==0 && nod!=T)
    {
        delete nod;
        return 1;
    }

    return 0;

}

int que(trie *nod, int poz)
{
    if(poz==l)
        return nod->k;

    if(nod->child[ss[poz]-'a'])
        return que(nod->child[ss[poz]-'a'], poz+1);

    return 0;
}

int pref(trie *nod, int poz)
{
    if(poz==l || nod->child[ss[poz]-'a']==NULL)
        return poz;

    return pref(nod->child[ss[poz]-'a'], poz+1);

}

int main()
{

    while(fi>>w>>ss)
    {
        l=ss.size();
        if(w==0)
            push(T,0);
        if(w==1)
            pop(T,0);
        if(w==2)
            fo<<que(T,0)<<'\n';
        if(w==3)
            fo<<pref(T,0)<<'\n';

    }

    return 0;
}