प्रिफिक्स खोज (Prefix Search)

आपके पास एक शब्दकोश है, जिसमें शुरुआत में कोई शब्द नहीं होता। आपको कुछ क्वेरीज़ की एक शृंखला पर कार्य करना है, और ये क्वेरीज़ दो प्रकार की होंगी:

1. Type 1 query: किसी शब्द को शब्दकोश में जोड़ना।

   • 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: ऐसे शब्दों की संख्या ढूंढना जो किसी दिए गए प्रिफिक्स से शुरू होते हों।

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

- Input: 2 prefix (1 ≤ |prefix| ≤ 1000), जहाँ prefix भी छोटे अंग्रेज़ी अक्षरों से बना एक गैर-रिक्त स्ट्रिंग है।

इनपुट

इनपुट की पहली पंक्ति में एक एकल पूर्णांक n (1 ≤ n ≤ 100000) आता है, जो क्वेरीज़ की संख्या दर्शाता है।

अगली n पंक्तियाँ क्वेरीज़ को दर्शाती हैं। प्रत्येक पंक्ति निम्न स्वरूपों में से किसी एक में होगी:

• 1 word (Type 1 query के लिए)

• 2 prefix (Type 2 query के लिए)

यह भी गारंटी है कि इनपुट में वर्णों की कुल संख्या 10^6 से ज़्यादा नहीं होगी।

आउटपुट

प्रत्येक Type 2 query के लिए, नई पंक्ति में उन शब्दों की संख्या प्रिंट करें जो दिए गए प्रिफिक्स से शुरू होते हैं।

उदाहरण