在一棵树上住着 N 个部落（编号为 1 \sim N），通过 N-1 条边连接在一起。
每个部落有一定的战斗力，第 i 个部落的战斗力为 A_i。如果两个部落通过边直接相连，且两个部落的战斗力不互质（即：满足最大公约数不为 1），则这两个部落可以结为联盟。
多个部落如果战斗力两两不互质，且多个部落在树上都相邻，即：形成联盟的部落中任意两个部落的路径上所有部落的战斗力都不互质，那么多个部落也可以结为联盟。
比如两个通过一条边相连的部落战斗力分别为 20 和 15，这两个部落可以结为联盟。再比如，两个通过一条边相连的部落的战斗力分别为 15 和 9，这两个部落也可以结为联盟。
但请注意：如果三个部落的战斗力分别为 20 15 9，部落 1 和部落 2 有边连接，部落 2 和部落 3 有边连接，部落 1 和部落 3 没有边连接，那么战力为 15 的部落，可以和战力为 20 的部落结为联盟，也可以和战力为 9 的部落结为联盟。但是三个部落无法同时结为联盟，因为他们的最大公约数为 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。