#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");
int len, t;
string s;
class trie
{
public:
    char val=666;
    int freq=0;
    vector<trie*> v;
};

trie *head = new trie;
vector<trie*>::iterator it;

void update_trie()
{
    trie *p = head;
    for(int i=2; i<len; ++i)
    {
        int tst=0;
        if(!p->v.size())
        {
            trie *add = new trie;
            add->val=s[i];
            p->v.push_back(add);
            p=add;
            if(i==len-1)(p)->freq++;
            continue;
        }
        else
            for(it=(p->v.begin()); it!=(p->v.end()); ++it)
                if(p->v.size()&&(*it)->val==s[i])
                {
                    if(i==len-1)(*it)->freq++;
                    p=*it;
                    tst=1;
                    break;
                }
        if(!tst)
        {
            trie *add = new trie;
            add->val=s[i];
            p->v.push_back(add);
            p=add;
            if(i==len-1)p->freq++;
        }
    }
}

void del_word()
{
    trie *p=head;
    trie *del=head;
    for(int i=2; i<len; ++i)
        for(it=(p->v.begin()); it!=(p->v.end()); ++it)
        {
            if((*it)->val==s[i])
            {
                if(p->v.size()>1) del=*it;
                p=*it;
                break;
            }
        }
    if(p->v.size())
    {
        p->freq--;
        return;
    }
    else
    {
        if(p->freq>1) p->freq--;
        else
        {
            while(del->v.size())
            {
                p=del;
                del=del->v.front();
                delete p;
            }
            delete del;
        }
    }
}

int frequency()
{
    trie *p=head;
    for(int i=2; i<len; ++i)
    {
        t=0;
        for(it=(p->v.begin()); it!=(p->v.end()); ++it)
        {
            if((*it)->val==s[i])
            {
                t=1;
                p=*it;
                break;
            }
        }

        if(!t)
            return 0;
    }

    return p->freq;
}

int prefix()
{
    trie *p=head;
    for(int i=2; i<len; ++i)
    {
        t=0;
        for(it=(p->v.begin()); it!=(p->v.end()); ++it)
            if((*it)->val==s[i])
            {
                p=*it;
                t=1;
                break;
            }
        if(!t)
        {
            return i-2;
        }
    }



    return len-2;
}

int main()
{
    while(getline(f, s))
    {
        len=s.size();
        if(s[0]=='0')
            update_trie();
        if(s[0]=='1')
            del_word();
        if(s[0]=='2')
            g<<frequency()<<'\n';
        if(s[0]=='3')
            g<<prefix()<<'\n';
    }



    return 0;
}