Migrated from Lutece 3253 emotional flutter

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

舞い上がれ 空高く
在那片高空之上 高昂地飞舞着
翼など 無くても
即使没有着那双翅膀

雨宫优子有一棵由 $n$ 个节点构成的树，其中编号为 $i$ 的点权值为 $a_i$。

对于一个三元组 $(x,y,z)$ ，满足 $1\le x<y<z\le n$，定义 $f(x,y,z)$ 为树上连通编号为 $x,y,z$ 这三个点的连通块的最少边数。

同时定义 $g(x,y,z)$ 为 $\gcd(a_x,a_y,a_z)$ 所含的不同质因子个数。

现在优子想要知道以下式子

对 $998244353$ 取模的结果。

Input

输入的第一行包括一个正整数 $n$，表示这棵树的点数。

第二行有一个长为 $n$ 的序列 $\{a_n\}$，表示树上每个点的点权。

接下来的 $n-1$ 行每行包括两个正整数 $x,y$，代表一条连接 $x$ 与 $y$ 的树边。

保证输入的数据构成一棵树。

Output

输出一行一个整数，表示上述式子对 $998244353$ 取模后的值。

Samples

3
1 2 3
1 2
2 3

0

4
6 14 6 6
1 2
2 3
2 4

12

Constraints

$1\le n,a_i\le 2\times 10^5$