#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("trie.in");
ofstream g("trie.out");

struct Trie
{
   int info,pref;
   Trie* urm[26];
}*p;
char s[22];
int n;

void operatie0()
{
    Trie* cap = p;
    int c,k = 0;

    while( k < n )
    {
        c = s[k] - 97;

        if( cap->urm[c] == NULL )
        {
            cap->urm[c] = new Trie;
            cap->urm[c]->info = 0;
            cap->urm[c]->pref = 0;

            for(int i = 0 ; i <= 25 ; i++  )
                cap->urm[c]->urm[i] = NULL;
        }

        cap->urm[c]->pref++;

        if( k == n-1 )
          cap->urm[c]->info++;

        cap = cap->urm[c];
        k++;
    }
}

void operatie1()
{
    Trie* cap = p;
    Trie* ant = p;
    Trie* aux;
    int a,c,k = 0,ok = 0;

    c = s[k] - 97;
    cap = cap->urm[c];

    while( cap!=NULL && k < n )
    {
        cap->pref--;
        if( cap->pref == 0 )
        {
          aux = cap;
          ok ++;
        }

        if( k == n-1 )
          cap->info--;

        a = s[k] - 97;
        k++;
        c = s[k] - 97;
        cap = cap->urm[c];

        if( ok == 0 )
        ant = ant->urm[a];
        else
        if( ok == 1 )
        ant->urm[a] = NULL;

        delete aux;
    }
}

void operatie2()
{
    Trie* cap = p;
    int c,k = 0;
    int o2 = 0;

    while( cap != NULL && k < n )
    {
        c = s[k] - 97;

        if( cap->urm[c] != NULL )
        if( k == n-1 )
           o2 = cap->urm[c]->info;

        cap = cap->urm[c];
        k++;
    }

    g<<o2<<'\n';
}

void operatie3()
{
    Trie* cap = p;
    int c,k = 0;
    int o3 = 0 ;

    while( cap!=NULL && k < n )
    {
        c = s[k] - 97;

        if( cap->urm[c] != NULL )
          if( cap->urm[c]->pref > 0 )
             o3 = k+1;

        cap = cap->urm[c];
        k++;
    }

    g<<o3<<'\n';
}

int main()
{
    int o;
    p = new Trie;
    for(int i = 0 ; i <= 25 ; i++  )
        p->urm[i] = NULL;

    while(f>>o)
    {
        f>>s;
        n = strlen(s);

        if( o == 0 )
          operatie0();
        else
        if( o == 1 )
          operatie1();
        else
        if( o == 2 )
          operatie2();
        else
        if( o == 3 )
          operatie3();
    }

    return 0;
}