"Дезоксирибонуклеїнова кислота"
Наука рухається вперед, і біологія не є винятком. Декодування ДНК стало одним з переломних моментів в історії біології. Один з студентів старшого курсу біологічного факультету, Джордж, вирішив зробити свій внесок у цю захоплюючу науку. Джордж планує розробити базу даних для зберігання генетичних кодів ДНК. Вам доручено реалізувати програму, яка додає коди до бази даних і повертає кількість кодів, для яких даний код є префіксом.
Код А довжиною N є префіксом коду B довжиною M, якщо N < M і перші N символів коду B дорівнюють коду А. Для зручності ДНК код представлений непорожнім рядком символів 'a', 'b', 'c', 'd'. База даних Джорджа повинна коректно обробляти дубльовані ДНК коди.
Вхідні дані
Перший рядок вхідних даних містить ціле число T – кількість операцій з базою даних. Наступні T рядків містять по одній операції кожен. Операція вставки складається з символу "+" за яким слідує ДНК код, який потрібно додати до бази даних, операція запиту складається з символу "?" за яким слідує ДНК код, для якого потрібно знайти кількість кодів з бази даних, що мають цей код як префікс.
Вихідні дані
Для кожного рядка на вході, який починається з символу "?", потрібно надрукувати результат у окремому рядку на виході.
Обмеження
Загальна довжина кодів у базі даних Джорджа не перевищує 1000000.