一组正整数 $S$ 的最大公约数 (GCD) 定义为能整除 $S$ 中所有元素的最大正整数 $d$，例如 $\text{GCD}(10) = 10, \text{GCD}(6, 9) = 3, \text{GCD}(20, 12, 16, 36) = 4$。

在本题中，给定一棵包含 $N$ 个节点的树，每个节点编号从 $1$ 到 $N$，并被赋予一个正整数 $A_i$。你的任务是找到最大的子树，使得该子树中所有节点权值的 GCD 不为 $1$。如果不存在这样的子树，则输出 $0$。树 $T'$ 是树 $T$ 的子树，当且仅当 $T'$ 是 $T$ 的连通子集。子树的大小定义为该子树中节点的数量。

例如，考虑以下 $N = 7$ 个节点的树，其中 $A_{1..7} = \{10, 5, 8, 6, 10, 6, 4\}$。

在此示例中，共有 $15$ 个子树满足所有节点权值的 GCD 不为 $1$，即 $7$ 个大小为 $1$ 的子树，$4$ 个大小为 $2$ 的子树，$3$ 个大小为 $3$ 的子树，以及 $1$ 个大小为 $4$ 的子树（最大的）。最大的子树包含节点 $4, 5, 6, 7$，其权值的 GCD 为 $\text{GCD}(A_4, A_5, A_6, A_7) = \text{GCD}(6, 10, 6, 4) = 2$。

输入格式

输入第一行包含一个整数 $N$ ($2 \le N \le 100\,000$)，表示给定树的节点数。 下一行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le 10^6$)，表示第 $i$ 个节点的权值。 接下来的 $N - 1$ 行，每行包含两个整数 $u_j, v_j$ ($1 \le u_j < v_j \le N$)，表示连接节点 $u_j$ 和 $v_j$ 的边。保证给定的树是连通的。

输出格式

输出一行，包含一个整数，表示满足所有节点权值的 GCD 不为 $1$ 的最大子树的大小。如果不存在这样的子树，则输出 $0$。

样例

样例输入 1

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

样例输出 1

4

说明 1

这是题目描述中的示例。

样例输入 2

4
1 1 1 1
1 2
2 3
3 4

样例输出 2

0

说明 2

在这种情况下，不存在所有节点权值的 GCD 不为 $1$ 的子树。

样例输入 3

5
100 100 100 100 100
3 4
1 2
3 5
2 4

样例输出 3

5