Recently, there has been a breach of user information from the mega-popular social network Secret Network. Among the confidential information are the passwords of all users.

Mihael, a young student who has been exploring computer security lately, found the whole thing really interesting. While experimenting with the social network, he found another security breach! When you input any string of characters that contains a substring equal to the actual password, the login will be successful. For example, if the user whose password is abc inputs one of the strings abc, abcd or imaabcnema, the system will successfully log him in, whereas the login will fail for axbc.

Mihael will be given ~2~ types of queries:

1 str: Insert ~str~ into the password database.

2 str: Output the number of users that can log into an account that has password ~str~.

Input Specification

The first line will contain the positive integer ~Q~ ~(1 \le Q \le 100\,000)~, the number of queries.

The next ~Q~ lines will contain one of the above queries.

The passwords consist of at least one and at most 10 lowercase letters of the English alphabet.

Output Specification

For each type ~2~ query, output the number of users that can log into their accounts with ~str~ as the password.

Sample Input 1

5
1 aaa
2 aa
1 aa
2 aa
1 abb

Sample Output 1

1
2

Sample Input 2

4
1 x
1 x
1 xy
2 x

Sample Output 2

3

Sample Input 3

7
1 mir
1 mirta
1 ta
1 ir
1 t
2 t
2 mir

Sample Output 3

3
2