题目描述

给定一个具有 $N$ 个顶点的无向树。
将顶点标记为 Vertex $1$，Vertex $2$，$\\ldots$，Vertex $N$。对于每个 $1\\leq i\\leq N-1$，第 $i$ 条边连接了 Vertex $U_i$ 和 Vertex $V_i$。
此外，每个顶点都被赋予一个正整数：Vertex $i$ 被赋值为 $A_i$。

两个不同的顶点 $s$ 和 $t$ 之间的代价 $C(s,t)$ 定义如下。

假设 $p_1(=s)$，$p_2$，$\\ldots$，$p_k(=t)$ 是连接 Vertex $s$ 和 Vertex $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