問題文

$N$ 頂点からなる無向木が与えられます。
頂点を順に頂点 $1$, 頂点 $2$, $\\ldots$, 頂点 $N$ とすると、 $1\\leq i\\leq N-1$ について、$i$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。
また、それぞれの頂点には正整数が割り当てられており、 具体的には頂点 $i$ には $A_i$ が割り当てられています。

相異なる $2$ 頂点 $s$, $t$ 間のコスト $C(s,t)$ が次のようにして定められます。

頂点 $s$ と頂点 $t$ を結ぶ単純パス上の頂点を順に $p_1(=s)$, $p_2$, $\\ldots$, $p_k(=t)$ とする。 ここで、$k$ はパス上の(端点含む)頂点数である。
このとき、$C(s,t)=k\\times \\gcd (A_{p_1},A_{p_2},\\ldots,A_{p_k})$ で定める。
ただし、$\\gcd (X_1,X_2,\\ldots, X_k)$ で $X_1,X_2,\\ldots, X_k$ の最大公約数を表す。

$\\displaystyle\\sum_{i=1}^{N-1}\\sum_{j=i+1}^N C(i,j)$ を $998244353$ で割ったあまりを求めてください。

制約

• $2 \\leq N \\leq 10^5$
• $1 \\leq A_i\\leq 10^5$
• $1\\leq U_i<V_i\\leq N$
• 入力は全て整数である。
• 与えられるグラフは木である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\\cdots$ $A_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\\vdots$ $U_{N-1}$ $V_{N-1}$

出力

$\\displaystyle\\sum_{i=1}^{N-1}\\sum_{j=i+1}^N C(i,j)$ を $998244353$ で割ったあまりを出力せよ。

入力例 1

4
24 30 28 7
1 2
1 3
3 4

出力例 1

47

頂点 $1$ と頂点 $2$ 、頂点 $1$ と頂点 $3$ 、頂点 $3$ と頂点 $4$ がそれぞれ直接辺で結ばれています。 よって、コストはそれぞれ次のように求められます。

• $C(1,2)=2\\times \\gcd(24,30)=12$
• $C(1,3)=2\\times \\gcd(24,28)=8$
• $C(1,4)=3\\times \\gcd(24,28,7)=3$
• $C(2,3)=3\\times \\gcd(30,24,28)=6$
• $C(2,4)=4\\times \\gcd(30,24,28,7)=4$
• $C(3,4)=2\\times \\gcd(28,7)=14$

求める値は $\\displaystyle\\sum_{i=1}^{3}\\sum_{j=i+1}^4 C(i,j)=(12+8+3)+(6+4)+14=47$ を $998244353$ で割ったあまりの $47$ となります。

入力例 2

10
180 168 120 144 192 200 198 160 156 150
1 2
2 3
2 4
2 5
5 6
4 7
7 8
7 9
9 10

出力例 2

1184