"Desoxyribonucleic Acid"

Science marches on and biology is not an exception. DNA decoding became one of turning points in history of biology. One of last year students of biology faculty, George, decided to make own contribution to this fascinating science. George plans to develop a database to store genetic codes of DNAs. You are assigned to implement a program, which adds codes to the database and returns number of codes for which give code is a prefix.

Code А of length N is a prefix of code B of length M if N < M and first N symbols of code B equal code А. For convenience DNA code is presented by non-empty string of characters 'a', 'b', 'c', 'd'. George’s database should correctly process duplicated DNA codes.

Input

The first input line contains integer T – number of database operations. Following T lines contain one operation each. Insert operation consists of symbol "+" followed by DNA code to be added to the database, query operation consists of symbol "?" followed by DNA code for which number of codes from the database having this code as prefix needs to be found.

Output

For each line at input, which starts from symbol "?" you need to print result into separate line at output.

Constraints

Total length of codes in George’s database does not exceed 1000000.