题目描述

给出一棵树，树有点权，求树上的一条链满足：链上所有点的点权的$gcd>1$且链上的点数最多．注意一个点也可以构成一条链．

输入格式：第一行一个整数n，代表节点数

第二行有n个整数，代表每个树的节点的点权， 后面n-1行，每行两个数字a，b，代表节点a到节点b有一条边

样例

样例输入1

3
1 2 3
1 2
2 3

样例输出1

1

样例输入2

3
2 3 4
1 3
2 3

样例输出2

2

样例输入3

3
1 1 1
1 2 
2 3

样例输出3

0

数据范围

• $n \leq 2 * 10^5$
• $1 \leq a_i \leq 2 * 10^5$