A. Iris 与树上的游戏

时间限制：2 秒
内存限制：256 MB

Iris 有一棵以顶点 $1$ 为根的树。每个顶点的值为 $0$ 或 $1$。

考虑树的一个叶子（顶点 $1$ 不被视为叶子），并定义它的权值：构造一个字符串，由从根到该叶子的路径上所有顶点的值依次组成。那么该叶子的权值等于字符串中 10 子串出现次数与 01 子串出现次数的差。

例如下面这棵树：绿色顶点值为 $1$，白色顶点值为 $0$。

• 计算叶子 $5$ 的权值：路径字符串为 10110，10 出现 $2$ 次，01 出现 $1$ 次，所以权值为 $2-1=1$。
• 计算叶子 $6$ 的权值：路径字符串为 101，10 出现 $1$ 次，01 出现 $1$ 次，所以权值为 $1-1=0$。

树的得分定义为树中权值非零的叶子数量。

但有些顶点的值尚未确定，会用 ? 表示。填满这些空缺太无聊了，于是 Iris 邀请 Dora 来玩游戏。

• 每轮，其中一名女孩选择一个剩余值为 ? 的顶点，并将其改为 $0$ 或 $1$。
• Iris 先手。
• 游戏持续到树中不再有值为 ? 的顶点为止。

Iris 的目标是最大化树的最终得分，而 Dora 的目标是最小化它。

假设两人都采取最优策略，请确定树的最终得分。

---

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 5 \cdot 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 树的顶点数。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示树中的一条边。

最后一行包含一个长度为 $n$ 的字符串 $s$，其中第 $i$ 个字符表示顶点 $i$ 的值。保证 $s$ 只包含 0、1 和 ?。

数据保证：所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

---

输出格式

对于每个测试用例，输出一个整数 —— 树的最终得分。

---

示例

输入

6
4
1 2
1 3
4 1
0101
4
1 2
3 2
2 4
???0
5
1 2
1 3
2 4
2 5
?1?01
6
1 2
2 3
3 4
5 3
3 6
?0????
5
1 2
1 3
1 4
1 5
11?1?
2
2 1
??

输出

2
1
1
2
1
0

---

样例解释

第一个测试用例：所有顶点的值都已确定。从根到叶子的路径有三条：

• 顶点 $1 \to 2$：路径字符串为 01，权值 $0-1=-1$
• 顶点 $1 \to 3$：路径字符串为 00，权值 $0-0=0$
• 顶点 $1 \to 4$：路径字符串为 01，权值 $0-1=-1$

因此有两个非零权值的叶子，树的得分为 $2$。

第二个测试用例：双方的一个最优选择序列可以是：

1. Iris 将顶点 $3$ 改为 $1$
2. Dora 将顶点 $1$ 改为 $0$
3. Iris 将顶点 $2$ 改为 $0$

最终只有叶子 $3$ 的权值非零，得分为 $1$。