题目描述

Maddy 碰到了朵朵绽放的荷花，但荷花之中又透露了一丝诡异……
在这个荷花池中，有一棵具有 $n$ 个结点的树，这是一个由 $n-1$ 条边连成的无向无环连通图。
每个结点 $i$ ($1 \le i \le n$) 都带有 $a_i$ 的权值，而一棵树的 $k$-点对 $(x, y)$ 定义如下：

• $1 \le x < y \le n$，$x$ 和 $y$ 是整数，表示树上的结点。
• 记树上的结点 $x$ 到结点 $y$ 之间的路径上的节点上的权值构成一个多重集合 $S$，注意 $a_x$ 和 $a_y$ 也算在路径上。
• 此时需要有 $\gcd S = \min S = k$，也即 $S$ 中元素的最大公因数等于 $S$ 中元素的最小值且为 $k$。

Maddy 现在在树上随机选取两个不同的点 $(x, y)$，如果存在 $k$ 满足 $(x, y)$ 是 $k$-点对，则她会得到 $k$ 个灯笼。
请帮助 Maddy 求出其期望获得的灯笼数 $q$ 对 $998244353$ 取模的值 $ans$，具体的输出要求请参照提示。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 10^5$)，表示数据组数。
每组测试数据输入的第一行输入一个整数 $n$ ($2 \le n \le 10^5$)，表示图的顶点数量。
随后 $n-1$ 行每行输入两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \ne v$)，表示树 $T$ 上存在一条 $u$ 到 $v$ 的边。
随后一行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) 分别表示树上点的权值。
保证所有测试数据输入中的 $\sum n \le 3 \times 10^5$，且每组数据输入的图构成一棵树。

输出格式

对于每组测试数据，输出一行一个整数 $ans$ 表示 Maddy 期望获得的灯笼数对 $998244353$ 取模的值。

1
6
1 2
1 3
2 4
2 5
3 6
6 2 3 4 2 1

332748119

提示

样例 1 解释

给定的树共有 6 个点，边为 $1-2, 1-3, 2-4, 2-5, 3-6,$

权值分别为 $a_1 = 6, a_2 = 2, a_3 = 3, a_4 = 4, a_5 = 2, a_6 = 1.$

我们枚举所有 $\binom{6}{2} = 15$ 对点，检查路径上的权值集合 $S$ 的 $\gcd(S)$ 与 $\min(S)$ 是否相等。
例如：

• 点对 $(1,2)$：路径为 $[6,2]$，$\min = 2$，$\gcd = 2$，因此属于 $k = 2$。
• 点对 $(1,3)$：路径为 $[6,3]$，$\min = 3$，$\gcd = 3$，因此属于 $k = 3$。
• 点对 $(1,6)$：路径为 $[6,3,1]$，$\min = 1$，$\gcd = 1$，因此属于 $k = 1$。
• 点对 $(3,4)$：路径为 $[3,6,2,4]$，$\min = 2$，$\gcd = 1$，不符合条件。

最终统计结果如下：
$k = 1$：5 对 $(1,6), (2,6), (3,6), (4,6), (5,6)$，
$k = 2$：6 对 $(1,2), (1,4), (1,5), (2,4), (2,5), (4,5)$，
$k = 3$：1 对 $(1,3)$，
$k = 4,5,6$：0 对。

可以求得对应的期望灯笼数为

$$\frac{5 \times 1 + 6 \times 2 + 1 \times 3 + 0 \times 4 + 0 \times 5 + 0 \times 6}{15} = \frac{4}{3}.$$

对应取模得到答案 $332748119$。

提示

可以证明本题的答案会是一个有理数，记这个答案是 $\frac{p}{q}$ 其中 $p, q$ 互质，你需要输出的数字 $ans$ 须满足在 $0 \le ans < 998244353$ 之内且

$$q \cdot ans \equiv p \pmod{998244353}.$$

可以证明这样的 $ans$ 在题目意义下一定存在。