#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIGMA 26


typedef struct trienod
{
	struct trienod *Vfii[SIGMA];
	char cuvant[30];
	int nrAp;
}TrieNod, *TrieArb;

TrieArb build(char * s)
{
	TrieArb nod = (TrieArb) calloc(1,sizeof(TrieNod));
	nod->nrAp = 0;
	if( s == NULL)
		nod->cuvant[0] = '\0';
	else
		strcpy(nod->cuvant,s);
	int  i = 0;
	for(i = 0 ; i < SIGMA; i++)
		nod->Vfii[i] = NULL;
	return nod;
}

int poz(char c)
{
	return c - 'a';
}


void Stergere(TrieArb root, char *s)
{
	int l = strlen(s);
	int i,p;
	for(i = 0; i < l; i++)
	{
		p = poz(s[i]);
		root = root->Vfii[p];
	}
	if(root->nrAp > 0)
		(root->nrAp)--;
}
int Ap(TrieArb root, char *s)
{
	int l = strlen(s);
	int p,i;
	for(i = 0 ; i < l ;i++)
	{
		p = poz(s[i]);
		if(root->Vfii[p] == NULL)
			return 0;
		root = root->Vfii[p];
	}
	return root->nrAp;
}

int Existenta(TrieArb nodb)
{
	if( nodb->nrAp > 0)
		return 1;

	int i;
	for(i = 0; i < SIGMA; i++)
	{
		if( nodb->Vfii[i] != NULL)
		{
			if( Existenta( nodb->Vfii[i]) == 1)
				return 1;
		}
	}
	return 0;	

}

int Prefix(TrieArb root, char *s)
{
	int l = strlen(s);
	int p,i;
	int lmax = 0;
	for( i = 0; i < l; i++)
	{
		p = poz(s[i]);
		if(root->Vfii[p] != NULL)
		{
			//printf(" aa\n");
			root = root->Vfii[p];
			if( Existenta(root))
				lmax = i +1;
			else
				break;
		}
		else
			break;
	}
	return lmax;
}

void Inserare(TrieArb root,char * s)
{
	int lung = strlen(s);
	int i =0;
	int p;
//	printf("a\n");
	for(i = 0; i < lung -1 ; i++)
	{
		p = poz(s[i]);
		if(root->Vfii[p] == NULL)
			root->Vfii[p] = build(NULL);
		root = root->Vfii[p];
	}
	p = poz(s[lung -1]);
	if(root->Vfii[p] == NULL)
		root->Vfii[p] = build(s);
	root = root->Vfii[p];
       (root->nrAp)++;
}





int main(void)
{
	FILE * fin = fopen("trie.in","rt");
	FILE * fout = fopen("trie.out","wt");
	int c, op,i = 0;
	char sir[30];
//	printf("ana");
	TrieArb root = build(NULL);
	//printf("al");
	while( (c= fgetc(fin)) != EOF)
	{

		if( c == '\n')
		{
			sir[i] = '\0';	
			//printf("%s\n",sir);
			switch(op){
				case 0: Inserare(root,sir);
					break;
				case 1: Stergere(root,sir);
					break;
				case 2: fprintf(fout,"%d\n",Ap(root,sir));
					break;
				case 3: fprintf(fout,"%d\n",Prefix(root,sir));
					break;
			}
			i = 0;
		}
		else
			if( c - '0' >= 0 && c - '0' <= 9)
			{
				op = c - '0';
			}
			else if( c - 'a' >= 0 && c - 'z' <= 0)
			{
				sir[i] = (char)c;
				i++;
			}

	}
	fclose(fin);
	fclose(fout);

	return 0;

}