在一家快速发展的公司中，经常会有新员工入职。每位新员工 $p$ 都会被分配一位直接上级，该上级的上级（无论是直接还是间接）都会成为 $p$ 的间接上级。

我们将 $p$ 的直接上级称为 $0$ 级上级。$0$ 级上级的上级被称为 $1$ 级上级。通常情况下，$k$ 级上级的上级被称为 $k+1$ 级上级。通过这种方式，员工是其直接上级及更高等级上级的下属。这定义了所有员工的层级关系，公司创始人位于层级顶端。

公司自成立以来所有入职员工的历史记录都被保存了下来。一些员工想知道他们有多少下属，且他们是这些下属的 $k$ 级上级。你能编写一个程序来帮助他们解决这个问题，以便他们能回到工作中吗？

输入格式

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 10^{5}$)，表示事件的数量。接下来的 $n$ 行按时间顺序描述了这些事件，每行一个。

雇佣新员工的事件由字符 'Z' 和两个整数 $p_{i}$ 与 $s_{i}$ ($2 \le p_{i} \le 10^{5}$，$p_{i} \neq p_{j}$，当 $i \neq j$ 时) 描述，分别代表新员工的编号及其直接上级的编号。$s_{i}$ 是当前已入职的某位员工的编号。创始人的编号为 $1$。

员工 $q_{i}$ 关于其有多少下属且他是这些下属的 $k_{i}$ 级上级的询问，由字符 'P' 和两个整数 $q_{i}$ 与 $k_{i}$ ($1 \le q_{i} \le 10^{5}$，$0 \le k_{i} \le 10^{5}$) 描述。

在第一个事件发生前，公司只有创始人一人。

输出格式

对于每位员工的询问，在标准输出中输出一行，包含一个整数，表示该员工有多少下属，且他是这些下属的 $k_{i}$ 级上级。

样例

输入 1

8
Z 2 1
P 1 0
Z 3 1
Z 4 2
P 1 1
P 1 0
Z 5 2
P 2 0

输出 1

1
1
2
2