Word Prefix Frequency Query System

You are required to implement a system that supports two types of operations: adding words and querying the frequency of word prefixes. The operations work as follows:

1. Add Operation: An input line starting with 1 followed by a word. This operation adds the word to the system and increases the frequency count for each of its prefixes. For example, adding the word 'hello' increases the frequency of 'h', 'he', 'hel', 'hell', and 'hello' by 1.

2. Query Operation: An input line starting with 2 followed by a prefix. This operation queries the frequency of the specified prefix from all the words that have been added so far.

Input is provided via standard input and output via standard output. For each query operation, you should output the frequency count on a new line.

The formula for computing the frequency of a prefix ( p ) is given by: [ frequency(p) = \text{number of times a word with prefix } p \text{ has been added} ]

Implement the solution such that it can handle up to (10^5) operations efficiently.

inputFormat

The first line contains an integer (Q) ((1 \le Q \le 10^5)) representing the number of operations. The following (Q) lines each contain an operation in one of the following formats:

1 word

• Add the given word (consisting of lowercase letters) to the system.

2 prefix

• Query and output the frequency count of the given prefix.

outputFormat

For each query operation (a line starting with 2), print a single integer which is the frequency of the specified prefix. Each answer should be printed on a new line.## sample

4
1 hello
1 hell
2 he
2 hello

2
1