题目描述

在一棵树上住着 $N$ 个部落（编号为 $1 \sim N$），通过 $N - 1$ 条边连接在一起。

每个部落有一定的战斗力，第 $i$ 个部落的战斗力为 $A_i$。如果两个部落通过边直接相连，且两个部落的战斗力不互质（即：满足最大公约数不为 $1$），则这两个部落可以结为联盟。

多个部落如果战斗力两两不互质，且多个部落在树上都相邻，即：形成联盟的部落中任意两个部落的路径上所有部落的战斗力都不互质，那么多个部落也可以结为联盟。

给定 $N$ 个部落之间的 $N - 1$ 条边的关系和 $N$ 个部落的战斗力，请编程计算出树上最大的联盟中有几个部落？

输入格式

第 $1$ 行读入整数 $N$，代表部落的总数。

接下来读入 $N - 1$ 行，每行读入 $X, Y$，表示编号为 $X$ 的部落和编号为 $Y$ 的部落之间有一条边。

接下来一行，读入 $N$ 个整数，代表每个部落的战斗力。

输出格式

输出最大联盟中，部落的数量。

样例

输入

3
1 2
2 3
20 15 9

输出

2

输入

5
1 2
1 3
2 4
2 5
10 8 9 12 10

输出

4

输入

10
4 1
1 3
3 8
8 7
7 9
3 5
4 2
9 6
8 10
10 20 5 40 25 12 9 35 15 6

输出

6

数据范围

对于 $15\%$ 的数据，满足 $1 \le N \le 1000$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le A_i \le 10^9$。