Deoxyribonucleic acid#1350
Science is ever-evolving, and biology is no exception. The discovery of DNA's structure marked a pivotal moment in biological history. Inspired by this, Hrytsko, a 10th-grade student, plans to develop a database for DNA genetic codes. Your task is to implement a program that can add codes to this database and count how many codes have a given code as their prefix.
Recall that a code of length is a prefix of code of length if the first characters of match code . For simplicity, a DNA code is represented as a non-empty string consisting of the characters 'a', 'b', 'c', 'd'. Hrytsko's database must handle identical DNA codes correctly.
The first line contains a natural number — the number of operations with the database. The next lines each contain one operation. An operation to add an element consists of the symbol <<\textbf{+}>> and the DNA code to be added to the database. A query operation consists of the symbol <<\textbf{?}>> and the DNA code for which you need to determine how many codes in the database have this code as a prefix.
The total length of all codes in Hrytsko's database does not exceed .
For each line of input beginning with the symbol <<\textbf{?}>>, output the answer on a separate line.
Example 1