CF1916G Optimizations From Chelsu

给定一棵包含 $n$ 个节点的树，节点编号从 $1$ 到 $n$。每条边标有一个整数权值 $w_i$。 定义 $len(u, v)$ 为节点 $u$ 到 $v$ 的简单路径上的边数，$g(u, v)$ 为 $u$ 到 $v$ 的简单路径上所有边权值的最大公约数。特别地，对于任意 $1 \leq u \leq n$，规定 $len(u, u) = 0$ 且 $g(u, u) = 0$。 请计算所有节点对 $(u, v)$ 中 $len(u, v) \cdot g(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 g(u, v)$ 的最大可能值。