给出一棵有 n 个节点且以 1 为根节点的树，每个节点有两个权值 a_i,b_i（1≤i≤n）。a_i 已经给出，b_i 初始为 0。
现在对于每一对节点 (u,v)（1≤u<v≤n），设 x=LCA(u,v)，如果 gcd(a_u,a_v)>1 那么 b_x←b_x+a_u×a_v，否则不做任何操作。
对于每个 1≤i≤n 求出 b_i mod 998244353。

第一行一个整数 n，表示有 n 个节点。
第二行 n 个正整数，表示 a₁,a₂…a_n。
接下来 n−1 行，每行两个正整数 u,v，表示节点 u 和节点 v 之间有一条边。

输出共 n 行，每行一个整数。
第 i 行表示 b_i 对 998244353 取模后的结果。

样例二：
输入：
15
73 83 31 9514 1189 43 79 2 2 1798 5063 2 5 2573 53 
1 2
2 3
1 4
4 5
1 6
3 7
5 8
5 9
6 10
7 11
10 12
9 13
7 14
13 15
输出：
23952214
633788
79763
38056
4
0
13027099
0
0
3596
0
0
0
0
0

建出的树如图。

有以下贡献：

• 对 $1$ 号节点：

$(3,4)$ 贡献 $4$。

$(3,5)$ 贡献 $4$。

$(3,7)$ 贡献 $144$。

$(3,8)$ 贡献 $48$。

$(1,6)$ 贡献 $9$。

$(1,7)$ 贡献 $216$。

$(1,8)$ 贡献 $72$。

$(6,7)$ 贡献 $216$。

$(6,8)$ 贡献 $72$。

总共 785。

• 对 $4$ 号节点：

$(4,5)$ 贡献 $4$。

$(4,7)$ 贡献 $144$。

$(4,8)$ 贡献 $48$。

$(5,8)$ 贡献 $48$。

$(7,8)$ 贡献 $1728$。

总共  $1972$。

• 对 5 号节点：

$(5,7)$ 贡献 $144$。

总共 $144$。

其他节点显然都为 $0$。