该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一颗包含$\red{n}$个节点的树，每个顶点$\red{i}$有一个权值$\red{a_i}$

我们定义$\red{g(x,y)}$为从$\red{x}$到$\red{y}$树上最短的路径上所有权值的最大公因数,$\red{dist(x,y)}$为从$\red{x}$到$\red{y}$树上最短路 径包含的顶点数。特殊的，$\red{dist(x,x)=1,}$求出在满足$\red{g(x,y)>1}$的前提下，$\red{dist(x,y)}$的最大值。

输入格式

第一行一个正整数$\red{n，}$表示节点数

第二行包含$\red{n}$个整数$\red{a_1,...,a_n,}$表示每个顶点的权值。

接下来的$\red{n-1}$行，每行包含两个整数$\red{x}$和$\red{y}$表示一条树边，保证最后形成一棵树。

输出格式

一行一个整数，如果不存在$\red{x,y}$使得$\red{g(x,y)>1，}$输出$\red{0,}$否则输出在满足$\red{g(x,y)>1}$的前提下，$\red{dist(x,y)}$ 的最大值。

样例

输入样例

3
2 3 4
1 2
2 3

输出样例

1

提示

对于$\red{50\%}$的数据，$\red{1<=n<=1000}$。

对于$\red{100\%}$的数据，$\red{1<=x,y<=n}$且$\red{x≠}$$\red{y,1<=n<=2\times 10^5,1<=a_i<=2\times 10^5}$。