Deoxyribonucleic acid
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 biology student, aims to contribute to this exciting field by creating a database for DNA genetic codes. Your task is to develop a program that can add codes to this database and count how many codes have a given code as their prefix.
Remember, a code A of length N is considered a prefix of code B of length M if the first N characters of B match code A. For simplicity, a DNA code is represented as a non-empty string consisting of the characters 'a', 'b', 'c', 'd'. Hrytsko's database must accurately handle identical DNA codes.
Input
The first line contains a natural number T, representing the number of operations on the database. Each of the following T lines contains a single operation. An operation to add a code is indicated by the symbol «+» followed by the DNA code to be added. A query operation is indicated by the symbol «?» followed by 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 will not exceed 1,000,000 characters.
Output
For each line of input that begins with the symbol «?», output the result on a separate line.