G. 来自 Chelsu 的优化
每个测试点时间限制：2 秒
内存限制：256 兆字节

给定一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。每条边有一个整数权值 $w_i$。

定义 $\operatorname{len}(u,v)$ 为顶点 $u$ 和 $v$ 之间简单路径上的边数，$\operatorname{gcd}(u,v)$ 为路径上所有边权值的最大公约数。例如，对于任意 $1 \le u \le n$，有 $\operatorname{len}(u,u)=0$，$\operatorname{gcd}(u,u)=0$。

你需要找到所有顶点对 $(u,v)$ 中 $\operatorname{len}(u,v) \cdot \operatorname{gcd}(u,v)$ 的最大值。

输入
每个测试包含多个测试用例。第一行一个整数 $t$（$1 \le t \le 10^4$）——测试用例个数。接下来是每个测试用例的描述。

每个测试用例的第一行一个整数 $n$（$2 \le n \le 10^5$）——树的顶点数。

接下来 $n-1$ 行，每行描述一条边：$u, v, w$（$1 \le u,v \le n$，$1 \le w \le 10^{12}$）。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出
对于每个测试用例，输出一个整数，表示所有顶点对中 $\operatorname{len}(u,v) \cdot \operatorname{gcd}(u,v)$ 的最大值。

示例
输入

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

输出

1000000000000
12
18
24