You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给你一棵有根的树，它由 n 个顶点组成，这些顶点的编号从 1 到 n 。根顶点为 1 。还有一个字符串 s 表示每个顶点的颜色：如果是 s[i]=B ，那么顶点 i 是黑色的；如果是 s[i]=W ，那么顶点 i 是白色的。

如果白顶点的数量等于黑顶点的数量，那么这棵树的子树就叫做平衡树。计算平衡子树的数量。

树是没有循环的连通无向图。有根树是指有一个选定顶点的树，这个顶点称为根。在本题中，所有树都有根 1 。

该树由包含 n−1 个数字的父数组 a2,…,an 指定： ai 是所有 i=2,…,n 的顶点 i 的父节点。顶点 u 的父顶点是 u 到根的简单路径上的下一个顶点。

顶点 u 的子树是在通往根的简单路径上经过 u 的所有顶点的集合。例如，在下图中， 7 位于 3 的子树中，因为简单路径 7→5→3→1 经过了 3 。请注意，顶点包含在其子树中，而根的子树就是整棵树。

图中显示的是 n=7 、 a=[1,1,2,3,3,5] 和 s=WBBWWBW 的树。顶点 3 处的子树是平衡的。

输入

第一行输入包含一个整数 t ( 1≤t≤1e4) - 测试用例数。

每个测试用例的第一行包含一个整数 n ( 2≤n≤4000 ) - 树中顶点的数量。 每个测试用例的第二行包含 n−1 个整数 a2,…,an ( 1≤ai<i ) --顶点的父节点 2,…,n 。

每个测试用例的第三行包含一个长度为 n 的字符串 s ，由字符 B 和 W 组成--树的着色。

保证所有测试用例中 n 的值之和不超过 2e5 。

Output

对于每个测试用例，输出一个整数 - 平衡子树的数量。

样例

3
7
1 1 2 3 3 5
WBBWWBW
2
1
BW
8
1 2 3 4 5 6 7
BWBWBWBW

2
1
4

样例解释

第一个测试案例如语句所示。只有顶点 2 和 3 的子树是平衡的。 在第二个测试案例中，只有顶点 1 的子树是平衡的。

在第三个测试案例中，只有顶点 1 、 3 、 5 和 7 的子树是平衡的。

限制

1s, 1024KiB for each test case.