Pesquisa por Prefixos

É-lhe fornecido um dicionário que inicialmente não contém nenhuma palavra. É necessário processar uma série de consultas, cada uma pertencendo a um de dois tipos:

1. Consulta de Tipo 1: Adicionar uma palavra ao dicionário.

   • Input: 1 word (1 ≤ |word| ≤ 1000), where word is a non-empty string consisting of lowercase English letters.

   • Action: Add the word to the dictionary.

2. Consulta de Tipo 2: Contar quantas palavras começam por um determinado prefixo.

   • Input: 2 prefix (1 ≤ |prefix| ≤ 1000), where prefix is a non-empty string consisting of lowercase English letters.

   • Output: Output the number of words in the dictionary that start with the given prefix.

- Entrada: 2 prefix (1 ≤ |prefix| ≤ 1000), onde prefix é uma cadeia de caracteres não vazia composta por letras minúsculas em inglês.

Entrada

A primeira linha da entrada contém um único inteiro, n (1 ≤ n ≤ 100 000), que representa o número de consultas.

As n linhas seguintes contêm as consultas, em um dos seguintes formatos:

• 1 word para uma consulta de Tipo 1.

• 2 prefix para uma consulta de Tipo 2.

Garante-se que o número total de caracteres na entrada não excede .

Saída

Para cada consulta de Tipo 2, escreva uma linha com um único inteiro que representa quantas palavras no dicionário começam pelo prefixo fornecido.

Exemplos