#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");

struct nod
{
    int cnt, nrfii;
    nod *fii[26];
    nod()
    {
        cnt=0;
        nrfii=0;
        for (int i=0; i<=25; i++)
        {
            fii[i]=nullptr;
        }
    }
};

void adaugaCuvant(nod *trie, string cuvant, int lit=0)
{
    if (lit==cuvant.size())
    {
        trie->cnt++;
    }
    else
    {
        char litcur=cuvant[lit];
        if (trie->fii[litcur-'a']==nullptr)
        {
            trie->fii[litcur-'a']=new nod;
            trie->nrfii++;
        }
        adaugaCuvant(trie->fii[litcur-'a'], cuvant, lit+1);
    }
}

int stergeCuvant(nod *trie, string cuvant, int lit=0)
{
    if (lit==cuvant.size())
    {
        trie->cnt--;
    }
    else
    {
        char litcur=cuvant[lit];
        int sters=stergeCuvant(trie->fii[litcur-'a'], cuvant, lit+1);
        if (sters==1)
        {
            trie->nrfii--;
            trie->fii[litcur-'a']=nullptr;
        }
    }
    if (trie->cnt==0 and trie->nrfii==0 and lit!=0)
    {
        delete trie;
        return 1;
    }
    return 0;
}

int aparitiiCuvant(nod *trie, string cuvant, int lit=0)
{
    if (lit==cuvant.size())
    {
        return trie->cnt;
    }
    else
    {
        char litcur=cuvant[lit];
        if (trie->fii[litcur-'a']==nullptr)
        {
            return 0;
        }
        return aparitiiCuvant(trie->fii[litcur-'a'], cuvant, lit+1);
    }
}

int prefixCuvant(nod *trie, string cuvant, int lit=0)
{
    if (lit==cuvant.size())
    {
        return lit;
    }
    else
    {
        char litcur=cuvant[lit];
        if (trie->fii[litcur-'a']==nullptr)
        {
            return lit;
        }
        return prefixCuvant(trie->fii[litcur-'a'], cuvant, lit+1);
    }
}

int caz;
string cuvant;
int main()
{
    nod *trie=new nod;
    while (fin>>caz>>cuvant)
    {
        if (caz==0)
        {
            adaugaCuvant(trie, cuvant);
        }
        else if (caz==1)
        {
            stergeCuvant(trie, cuvant);
        }
        else if (caz==2)
        {
            fout<<aparitiiCuvant(trie, cuvant)<<'\n';
        }
        else if (caz==3)
        {
            fout<<prefixCuvant(trie, cuvant)<<'\n';
        }
    }
    
    return 0;
}