接頭辞検索

最初は単語がまったく登録されていない辞書が与えられます。この辞書に対して、2種類のクエリを処理しなければなりません。

1. 種類1のクエリ: 辞書に単語を追加する

   • 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. 種類2のクエリ: 与えられた接頭辞 (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.

- 入力形式: 2 prefix (1 ≤ |prefix| ≤ 1000)

入力

最初の行に、クエリの数を表す整数 n (1 ≤ n ≤ 100000) が与えられます。

続く n 行にわたってクエリが与えられ、各行は以下のいずれかの形式になります:

• 1 word (種類1クエリ)

• 2 prefix (種類2クエリ)

また、入力全体で使われる文字の総数は を超えないことが保証されています。

出力

種類2のクエリに対して、それぞれ新しい行に1つ、prefix で始まる単語が辞書にいくつあるかを表す整数を出力してください。

例