# Arup Guha
# 1/24/2025
# Solution to Ind #4 Contest Problem: Strange Lottery Simulator

# To store a node.
class node:

    # Constructor
    def __init__(self):
        self.total = 0
        self.children = []
        for i in range(26):
            self.children.append(-1)

def insert(mytlist, name):

    # Where we start.
    curNode = 0
    mytlist[curNode].total += 1
    #print("name is",name)

    # Go through the letters.
    for i in range(len(name)):

        # Get the index of where the next node is.
        letNum = ord(name[i]) - ord('a')
        nextNode = mytlist[curNode].children[letNum]

        # This branch wasn't created yet, so add it to the list.
        if nextNode == -1:
            nextNode = len(mytlist)
            mytlist[curNode].children[letNum] = nextNode
            tmp = node()
            mytlist.append(tmp)
            #print("in if", tmp.children)

        # Update our current node, and its total count.
        curNode = nextNode
        #print("curNode is ",curNode)
        mytlist[curNode].total += 1

def query(mytlist, name):

    # Where we start.
    curNode = 0
    retval = 0
    
    # Go through the letters.
    for i in range(len(name)):

        # Get the index of where the next node is.
        letNum = ord(name[i]) - ord('a')
        nextNode = mytlist[curNode].children[letNum]

        # This branch doesn't exist so no word starts with this prefix.
        if nextNode == -1:
            return 0 

        # Update our current node
        curNode = nextNode
        retval = mytlist[curNode].total

    return retval

        
def main():

    nC = int(input())

    # Process cases.
    for loop in range(1,nC+1):

        # Case header.
        print("Lottery #", loop, ":", sep="")

        nOps = int(input())
        mytrie = [node()]
        revtrie = [node()]
        mode = True

        # Go through operations.
        for i in range(nOps):

            # Get info.
            toks = input().split()
            op = int(toks[0])

            # Mildly annoying.
            name = ""
            if op < 3:
                name = toks[1]

            # Insert into trie.
            if op == 1:

                # Regular order.
                if mode:
                    insert(mytrie, name)
                    insert(revtrie, name[::-1])

                # Flip it!
                else:
                    insert(mytrie, name[::-1])
                    insert(revtrie, name)

            # Query case.
            elif op == 2:

                # Regular query.
                if mode:
                    print(query(mytrie,name))

                # Reverse query.
                else:
                    print(query(revtrie,name))

            # Flip it.
            else:
                mode = not mode

        # Blank line after case.
        print()

# Run it.
main()