Prefix Search

You are given a dictionary that initially contains no words. You need to process a series of queries, each falling into one of two types:

1. Type 1 query: Add a word to the dictionary.

   • 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. Type 2 query: Count the number of words starting with a given prefix.

   • 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.

You need to implement a program that processes these queries efficiently.

Input

The first line of the input contains a single integer, n (1 ≤ n ≤ 100 000), representing the number of queries.

The following n lines contain the queries. Each line is in one of the following formats:

• 1 word for a Type 1 query.

• 2 prefix for a Type 2 query.

It is guaranteed that the total number of characters in the input does not exceed .

Output

For each Type 2 query, output a single integer on a new line representing the number of words in the dictionary that start with the given prefix.

Examples