题目描述

给定一棵有根树，树上共有 $N$ 个顶点，根为 $1$ 号点。每个顶点 $i$ 有一个整数权值 $A_i$。

在这棵有根树中，如果从顶点 $v$ 出发，只沿着从父亲到儿子的方向行走，可以到达顶点 $u$，那么称 $u$ 是 $v$ 的一个后代。

请你求一条最长的简单路径，使得：

• 路径从某个顶点出发，到达它的某个后代；
• 路径上所有顶点权值的最大公约数大于 $1$。

路径长度定义为路径上的边数。

如果不存在满足条件的正长度路径，则输出 $0$。

输入格式

第一行输入一个整数 $N$，表示树的顶点数。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示每个顶点的权值。

接下来 $N-1$ 行，每行输入两个整数 $x,y$，表示树中有一条连接 $x$ 和 $y$ 的无向边。树以 $1$ 号点为根。

输出格式

输出一行一个整数，表示满足条件的最长路径长度。

数据范围

• $1\le N\le 10^5$
• $1\le A_i\le 2\times 10^6$

子任务

只有通过某个子任务及其依赖子任务的所有测试，才能获得该子任务的分数。

样例 1

输入

8
7 6 9 2 4 8 9 9
1 2
1 3
2 4
2 5
2 6
3 7
7 8

输出

2

说明

唯一的最优路径是 $3\to 7\to 8$，长度为 $2$，路径上顶点权值的最大公约数为 $9$。

样例 2

输入

8
3 6 4 8 7 9 9 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8

输出

2

说明

此时树是一条链。唯一的最优路径是 $2\to 3\to 4$，长度为 $2$，路径上顶点权值的最大公约数为 $2$。