在Dengkleknesia国家,有$$$N$$$工厂,编号从$$$1$$$到$$$N$$$。工厂 $$$i$$$ 的电气系数为 $$$A_i$$$。还有$$$N-1$$$电源线,第$$$j$$$电源线连接工厂$$$U_j$$$和工厂$$$V_j$$$。可以保证Dengkleknesia的每个工厂都通过一根或多根电源线与Dengkleknesia的所有其他工厂相连。换句话说,工厂的集合形成了一棵树。 Dengkleknesia 的每一对不同工厂都可以使用一条或多条现有电力线相互传输电力。然而,每条电源线都需要先打开,以便电力可以通过。
将 $$$f(x, y, z)$$$ 定义为工厂 $$$x$$$ 可以向工厂 $$$y$$$ 和工厂 $$$z$$$ 进行电力传输所需打开的最少电源线数量。还将 $$$g(x, y, z)$$$ 定义为 $$$\text{GCD}(A_x, A_y, A_z)$$$ 的不同素因数的数量。
要测量电效率,您必须找到 $$$(x, y, z)$$$ 的所有组合的 $$$f(x, y, z) \times g(x, y, z)$$$ 之和,使得 $$$1 \leq x < y < z \leq N$$$。因为答案可能非常大,所以您只需输出对 $$$998\,244\,353$$$ 取模的答案。
注: $$$\text{GCD}(k_1, k_2, k_3)$$$ 是 $$$k_1$$$、$$$k_2$$$ 和 $$$k_3$$$ 的最大公约数,它是同时整除 $$$k_1$$$、$$$k_2$$$ 和 $$$k_3$$$ 的最大整数。
输入
第一行包含一个整数 $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — Dengkleknesia 的工厂数量。
第二行包含 $$$N$$$ 整数 $$$A_1, A_2, \dots, A_N$$$ ($$$1 \leq A_i \leq 2 \cdot 10^5$$$) — 工厂的电气系数。
接下来的 $$$N-1$$$ 行中的第 $$$j$$$ 行包含两个整数 $$$U_j$$$ 和 $$$V_j$$$ ($$$1 \le U_j, V_j \le N$$$) — 连接城市 $$$U_j$$$ 和 $$$V_j$$$ 的电源线。工厂的集合形成一棵树。
输出
一个整数,表示 $$$(x, y, z)$$$ 的所有组合的 $$$f(x, y, z) \times g(x, y, z)$$$ 之和,使得 $$$1 \leq x < y < z \leq N$$$,模 $$$998\,244\,353$$$
示例
输入 #1
3 1 2 3 1 2 2 3
输出 #1
0
输入 #2
4 6 14 6 6 1 2 2 3 2 4
输出 #2
12
注意
在第一个示例中,唯一可能的 $$$(x, y, z)$$$ 是 $$$(1, 2, 3)$$$。因为 $$$\text{GCD}(A_1, A_2, A_3) = \text{GCD}(1, 2, 3) = 1$$$ 具有 $$$0$$$ 不同的质因数,因此 $$$f(x, y, z) \times g(x, y, z) = 2 \times 0 = 0$$$。
在第二个示例中,满足条件的所有三元组 $$$(x, y, z)$$$ 如下:
- $$$(1, 2, 3) \rightarrow f(1, 2, 3) \times g(1, 2, 3) = 2 \times 1 = 2$$$
- $$$(1, 2, 4) \rightarrow f(1, 2, 4) \times g(1, 2, 4) = 2 \times 1 = 2$$$
- $$$(1, 3, 4) \rightarrow f(1, 3, 4) \times g(1, 3, 4) = 3 \times 2 = 6$$$
- $$$(2, 3, 4) \rightarrow f(2, 3, 4) \times g(2, 3, 4) = 2 \times 1 = 2$$$
因此电效率为 $$$2 + 2 + 6 + 2 = 12$$$。