Description

小A正在曹妃甸区，曹妃甸区位于唐山，唐山这个城市有 $n$ 个路口，$n-1$ 条道路，并且保证任意两个路口互相联通。每个路口根据妈妈审美的不同都有一个优雅值，而如果两个相邻的路口的优雅值存在至少两个共同的质因子$p$和$q$（$p\neq q$）则这两个相邻的路口就是共同优雅的。

现在曹妃甸的小A将共同优雅联通块定义为：在城市中选取若干个路口，若这些路口们两两互相联通，且每两个相邻的路口都是共同优雅的，则该联通块称为共同优雅联通块。

注意：单独的一个路口也符合共同优雅联通块的定义。

现在位于曹妃甸的小A想知道，整个城市的最大优雅联通块包含多少个路口。

Input Format

第一行一个正整数$n(1 \le n \le 10^6)$ 表示有 $n$ 个路口。

第二行 $n$ 个整数，第 $i$ 个整数为 $a_i(1\le a_i\le 5 \times10^6)$ 表示该路口的优雅值。

接下来 $n-1$ 行，每行两个整数 $x$,$y(1 \le x,y \le n)$ 表示 $x$ 路口到 $y$ 路口有一条道路。

Output Format

一行一个整数，表示最大优雅联通块包含多少个路口。

4
12 12 4 18
1 2
1 3
2 4​

3​

Hint

最大优雅联通块为 1,2,4三个路口所在的联通块,两两相邻的路口均包含 2,3 两个质因子.

Source

线性筛 并查集 gcd