Fish 拥有一棵包含 $N$ 个节点的树，节点编号从 $1$ 到 $N$，每个节点上都有一个标签。这些标签是 $1$ 到 $N$ 之间的整数。现在 Fish 想要将这棵树划分为多个部分，使得每个部分都是树的一个连通分量。实现的方法有很多种，对吧？但现在 Fish 定义，如果一个部分中至少有一个标签仅在该部分中出现，则称该部分为“好”部分。

请告诉 Fish 在一次划分中，他最多能得到多少个“好”部分。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例： 第一行包含一个整数 $N$。 第二行包含 $N$ 个整数，表示每个节点的标签。 接下来 $N - 1$ 行，每行包含两个数字 $a, b$，表示节点 $a$ 和节点 $b$ 之间有一条边。

输出格式

对于每个测试用例，输出 Case x: y，其中 $x$ 表示从 $1$ 开始的测试用例编号，$y$ 是 Fish 在一次划分中最多能得到的“好”部分的数量。

样例

样例输入 1

2
6
1 1 2 2 3 3
1 2
2 3
2 4
1 5
5 6
6
1 1 2 2 3 3
1 2
1 3
3 4
1 5
5 6

样例输出 1

Case 1: 2
Case 2: 3

说明

$1 \le T \le 100$ $1 \le N \le 10^5$ $1 \le a, b \le N$ 对于 $90\%$ 的测试用例：$N \le 1000$