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$) —— 表示节点 $u$ 和 $v$ 之间的一条边。

保证给定的边构成一棵树。

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

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

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

样例

输入 1

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
??

输出 1

2
1
1
2
1
0

说明

在第一个测试用例中，所有节点的值都已确定。从根节点到叶子节点有三条不同的路径：

• 从节点 $1$ 到节点 $2$。路径形成的字符串为 01，因此叶子节点的权重为 $0 - 1 = -1$。
• 从节点 $1$ 到节点 $3$。路径形成的字符串为 00，因此叶子节点的权重为 $0 - 0 = 0$。
• 从节点 $1$ 到节点 $4$。路径形成的字符串为 01，因此叶子节点的权重为 $0 - 1 = -1$。

因此，有两个权重非零的叶子节点，所以树的得分为 $2$。

在第二个测试用例中，两个玩家的一种最优选择序列可以为：

• Iris 选择将节点 $3$ 的值更改为 $1$。
• Dora 选择将节点 $1$ 的值更改为 $0$。
• Iris 选择将节点 $2$ 的值更改为 $0$。

最终的树如下所示：

唯一权重非零的叶子节点是 $3$，因此树的得分为 $1$。注意，这可能不是 Iris 和 Dora 的唯一最优选择序列。