class Node:
    def __init__(self, children: dict = None, end: bool = False, count: int = 0):
        self.children = children if children else dict()
        self.endOfWord = end
        self.countOfWords = count
        
class Contacts:
    def __init__(self, node: Node = None):
        self.root = node if node else Node()
    
    def find(self, word):
        root: Node = self.root
        for ch in word:
            if ch not in root.children:
                return 0
            root = root.children[ch]
        return root.countOfWords
    
    def add(self, word):
        root: Node = self.root
        for ch in word:
            if ch not in root.children:
                root.children[ch] = Node()
            root.countOfWords += 1
            root = root.children[ch]
        root.endOfWord = True
        root.countOfWords += 1
        return root.countOfWords
    
def contacts(queries):
    # Write your code here
    contacts = Contacts()
    output = []
    
    for query in queries:
        if "add" == query[0]:
            contacts.add(query[1])
        else:
            output.append(contacts.find(query[1]))
    return output

# Brute Force Solution (Not recommended because of time complexity)
# def contacts(queries):
#     # Write your code here
#     contacts = []
#     output = []
    
#     for query in queries:
#         if "a" == query[0]:
#             contacts.append(query[4:])
#         else:
#             search = query[5:]
#             n = len(search)
#             count = 0
#             for contact in contacts:
#                 if contact[:n] == search:
#                     count+=1
#             output.append(count)
#     print(contacts)
#     return output