给你一棵有 $$$n$$$ 个顶点的树,其顶点编号从 $$$1$$$ 到 $$$n$$$。每条边都标有某个整数 $$$w_i$$$。
将 $$$len(u, v)$$$ 定义为顶点 $$$u$$$ 和 $$$v$$$ 之间的简单路径中的边数,并将 $$$gcd(u, v)$$$ 定义为顶点 $$$u$$$ 和 $$$v$$$ 之间的简单路径的边上写入的所有数字的最大公约数。例如,对于任何 $$$1 \leq u \leq n$$$,$$$len(u, u) = 0$$$ 和 $$$gcd(u, u) = 0$$$。
您需要找到树中所有顶点对 $$$len(u, v) \cdot gcd(u, v)$$$ 的最大值。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。接下来是他们的描述。
每个测试用例的第一行包含数字 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 树中的顶点数。
接下来的 $$$n-1$$$ 行以 $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq w \leq 10^{12}$$$) 的格式指定边。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出一个等于树中所有顶点对 $$$len(u, v) \cdot gcd(u, v)$$$ 最大值的数字。
示例
输入 #1
4 2 1 2 1000000000000 4 3 2 6 2 1 10 2 4 6 8 1 2 12 2 3 9 3 4 9 4 5 6 5 6 12 6 7 4 7 8 9 12 1 2 12 2 3 12 2 4 6 2 5 9 5 6 6 1 7 4 4 8 12 8 9 4 8 10 12 2 11 9 7 12 9
输出 #1
1000000000000 12 18 24