题目背景

SanhaiOJ 上的很多 Oler 经常遇到“代码调不过”的问题。
为了解决这一痛点，SanhaiOJ 上线了 SANHAI AI 求调服务 —— 用户只要跳转到 sanhai.iepose.cn，就能选择不同的 AI 模型来帮忙调试。

不过，AI 模型的数量实在太多了，用户在搜索模型时需要一个高效的方式来匹配模型名称。于是，SanhaiOJ 决定使用 Trie（前缀树） 来实现快速的前缀查询。

题目描述

你需要实现一个支持以下两种操作的数据结构：

1. 插入模型名称

   • 格式：insert name
   • 将字符串 name 插入到字典中。

2. 查询前缀

   • 格式：query prefix
   • 查询字典中有多少个字符串以 prefix 作为前缀。

请你编写程序，完成所有操作。

📥 输入格式

• 第一行一个整数 ( q ) (1 ≤ q ≤ 2×10^5)，表示操作次数。
• 接下来 q 行，每行一个操作，格式为：
  • insert name
  • query prefix
• 其中 name 和 prefix 均为仅包含小写字母的字符串，长度不超过 50。

📤 输出格式

• 对于每个 query 操作，输出一个整数，表示满足条件的字符串数量。

样例输入

6
insert sanhai
insert sanhaioj
insert san
query san
query sanh
query oj

样例输出

3
2
0

数据范围与提示

• 1 ≤ q ≤ 2×10^5
• 每次操作的字符串长度 ≤ 50
• 总输入规模 ≤ 10^7