该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

维护一个字符串集合，支持两种操作：插入字符串和查询字符串出现次数。 用字符 I 表示插入操作，后面跟随要插入的字符串 $s$ ；或者以字符 Q 表示查询操作，后面是要查询的字符串 $s$ ;对于每个查询操作，小飞侠需要计算并输出该字符串在集合中出现的次数。

输入格式

第一行包含整数 $q$，表示操作数。

接下来 $q$ 行，每行包含一个操作指令，指令为 I s 或 Q s 中的一种。

输出格式

对于每个询问指令 Q s，都要输出一个整数作为结果，表示 $s$ 在集合中出现的次数。

每个结果占一行。

数据范围

$1 ≤ q ≤ 10^3$

$1 ≤ |s| ≤ 10^3$

输入样例：

10
Q kq
I fa
Q xc
I fa
I fa
Q fa
I nv
Q g
Q fa
Q e

输出样例：

0
0
3
0
3
0