弗拉迪斯拉夫有一个非常想去麻省理工学院的儿子。麻省理工学院(摩尔多瓦理工学院)的大学宿舍可以表示为一棵具有 $$$n$$$ 个顶点的树,每个顶点都是一个只有一个学生的房间。树是一个连通的无向图,具有 $$$n$$$ 个顶点和 $$$n-1$$$ 个边。
今晚,有三类学生:
- 想要聚会和演奏音乐的学生(用 $$$\texttt{P}$$$ 标记),
- 想要睡觉并享受安静的学生(标记为 $$$\texttt{S}$$$),以及
- 不关心的学生(用$$$\texttt{C}$$$标记)。
最初,所有边缘都是薄墙,可以让音乐穿过,所以当聚会的学生放音乐时,每个房间都会听到它。但是,我们可以在任何边缘放置一些厚墙 - 厚墙不允许音乐穿过它们。
大学想安装一些厚墙,以便每个聚会的学生都可以播放音乐,而昏昏欲睡的学生都听不到。
因为大学在命名权诉讼中损失了很多钱,所以他们要求您找到他们需要使用的最少厚墙数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 树中的顶点数。
每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$a_2, \dots , a_n$$$ ($$$1 \leq a_i < i$$$) - 这意味着树中 $$$i$$$ 和 $$$a_i$$$ 之间有一条边。
每个测试用例的第三行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 $$$\texttt{P}$$$、$$$\texttt{S}$$$ 和 $$$\texttt{C}$$$ 组成,表示学生 $$$i$$$ 的类型为 $$$s_i$$$。
所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - 所需厚墙的最小数量。
示例
输入 #1
3 3 1 1 CSP 4 1 2 2 PCSS 4 1 2 2 PPSS
输出 #1
1 1 2
注意
在第一种情况下,我们可以在房间$$$1$$$和$$$2$$$之间安装一堵厚墙,如下所示。我们不能安装 $$$0$$$ 墙,因为这样来自房间 3 的音乐会到达学生想要睡觉的房间 2,所以答案是 $$$1$$$。还有其他有效的解决方案。