Typeahead Search

Manao is a web developer building a typeahead search prototype.
He is given:

A set of search keywords (all distinct).
A sequence of user actions in the search box.

Each action is either:

typing a lowercase Latin letter (a–z), which appends it to the current text, or
pressing backspace (<), which deletes the last character

After every action, if the current text length is at least 3, output how many keywords start with the current text.
If the length is less than 3, output nothing for that action.

Constraints

Number of keywords $1 \leq N \leq 100$
Each keyword: lowercase Latin letters, at most 20 characters long, all keywords are distinct
The sequence of user actions is at most $1000$ characters long; characters are a–z or <
Backspace is never applied when the current text is empty

Input Format

First line: integer $N$ — number of keywords
Next $N$ lines: one keyword per line
Next line: $=====$
Next line: the actions sequence (letters a–z and <)

Output Format

Print "Case #1:", followed by a newline. (This problem has a single testcase.)
For each action, if the current text length is $\geq 3$ , print a single line with one integer — the number of keywords that start with the current text.
For actions that leave the text shorter than 3, print nothing for that action.

Example

Input

4
pythonia
python
pythoner
geolymp
=====
pythonia<<<<<<<<geolymp

Output