第一个节点是0，边代表字符，son[p][u]表示当前在第p个节点处，查找边为u的#节点是否存在

b站讲解：

https://www.bilibili.com/video/BV1yA4y1Z74t/?spm_id_from=333.337.search-card.all.click&vd_source=fec447d8ebc27817e60a593e308f3847

N=int(1e5)
n=int(input())
son=[[0]*26 for _ in range(N)]
idx=0
cnt=[0]*N
def insert(string):
    global idx
    p=0
    for i in string:
        u=ord(i)-ord('a')
        if son[p][u]==0:
            idx+=1
            son[p][u]=idx
        p=son[p][u]
    cnt[p]+=1

def query(string):
    p=0
    for i in string:
        u=ord(i)-ord('a')
        if son[p][u]:
            p=son[p][u]
        else:
            return 0
    return cnt[p]

for i in range(n):
    ins=list(input().split(" "))
    if ins[0]=='I':
        insert(ins[1])
    if ins[0]=='Q':
        print(query(ins[1]))