#include <iostream>
#include <fstream>

using namespace std;
const int ALPHABET = 26;
struct elem
{
    elem* next[26]{};
    int nr = 0;
};
void Add(elem* varf,char* p)
{
    while(*p)
    {
        int index = *p-'a';
        if(!varf->next[index])
            varf->next[index] = new elem;
        varf = varf->next[index];
        p++;
    }
    varf->nr++;
}
bool Empty(elem* varf)
{
    if(varf->nr)
        return false;
    for(int i=0;i<ALPHABET;i++)
        if(varf->next[i])
            return false;
    return true;
}
elem* Delete(elem* varf,char* p)
{
    if(varf == NULL)
        return NULL;
    if(*p)
    {
        int index = *p - 'a';
        varf->next[index] = Delete(varf->next[index],p+1);
    }
    else
        varf->nr--;
    if(Empty(varf))
    {
        delete varf;
        return NULL;
    }
    else
        return varf;

}
int aparitii(elem* varf,char* p)
{
    while(*p)
    {
        int index = *p-'a';
        if(!varf->next[index])
            return 0;
        varf = varf->next[index];
        p++;
    }
    return varf->nr;
}
int prefix(elem* varf,char* p)
{
    int poz=0;
    for(poz=0;p[poz];poz++)
    {
        int index = p[poz] - 'a';
        if(!varf->next[index])
            return poz;
        varf = varf->next[index];
    }
    return poz;
}
int main()
{
    elem* varf = new elem;
    int operatie;
    char cuv[21];
    ifstream f("trie.in");
    ofstream g("trie.out");
    while(f>>operatie)
    {
        f>>cuv;
        switch(operatie)
        {
        case 0:
            Add(varf,cuv);
            break;
        case 1:
            if(Delete(varf,cuv) == NULL)
                varf = new elem;
            break;
        case 2:
            g<<aparitii(varf,cuv)<<'\n';
            break;
        case 3:
            g<<prefix(varf,cuv)<<'\n';
            break;
        }
    }
    f.close();
    g.close();
    return 0;
}