310980: CF1916G. Optimizations From Chelsu

G. Optimizations From Chelsutime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a tree with $n$ vertices, whose vertices are numbered from $1$ to $n$. Each edge is labeled with some integer $w_i$.

Define $len(u, v)$ as the number of edges in the simple path between vertices $u$ and $v$, and $gcd(u, v)$ as the Greatest Common Divisor of all numbers written on the edges of the simple path between vertices $u$ and $v$. For example, $len(u, u) = 0$ and $gcd(u, u) = 0$ for any $1 \leq u \leq n$.

You need to find the maximum value of $len(u, v) \cdot gcd(u, v)$ over all pairs of vertices in the tree.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. This is followed by their description.

The first line of each test case contains the number $n$ ($2 \leq n \leq 10^5$) — the number of vertices in the tree.

The next $n-1$ lines specify the edges in the format $u$, $v$, $w$ ($1 \leq u, v \leq n$, $1 \leq w \leq 10^{12}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single number equal to the maximum value of $len(u, v) \cdot gcd(u, v)$ over all pairs of vertices in the tree.

ExampleInput

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

Output

1000000000000
12
18
24

题目大意：
给定一棵有n个顶点的树，顶点编号从1到n。每条边标记有一个整数w_i。

定义len(u, v)为顶点u和v之间的简单路径上的边数，gcd(u, v)为顶点u和v之间的简单路径上所有边的标记数的最大公约数。例如，对于任意的1 ≤ u ≤ n，有len(u, u) = 0和gcd(u, u) = 0。

需要找到所有顶点对中len(u, v) * gcd(u, v)的最大值。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t (1 ≤ t ≤ 10^4) —— 测试用例的数量。接下来是它们的描述。

每个测试用例的第一行包含一个整数n (2 ≤ n ≤ 10^5) —— 树中的顶点数。

接下来的n-1行以u, v, w的格式指定边(1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^12)。

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

输出数据格式：
对于每个测试用例，输出一个数字，等于所有顶点对中len(u, v) * gcd(u, v)的最大值。题目大意： 给定一棵有n个顶点的树，顶点编号从1到n。每条边标记有一个整数w_i。 定义len(u, v)为顶点u和v之间的简单路径上的边数，gcd(u, v)为顶点u和v之间的简单路径上所有边的标记数的最大公约数。例如，对于任意的1 ≤ u ≤ n，有len(u, u) = 0和gcd(u, u) = 0。 需要找到所有顶点对中len(u, v) * gcd(u, v)的最大值。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t (1 ≤ t ≤ 10^4) —— 测试用例的数量。接下来是它们的描述。 每个测试用例的第一行包含一个整数n (2 ≤ n ≤ 10^5) —— 树中的顶点数。 接下来的n-1行以u, v, w的格式指定边(1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^12)。 保证所有测试用例的n之和不超过10^5。 输出数据格式： 对于每个测试用例，输出一个数字，等于所有顶点对中len(u, v) * gcd(u, v)的最大值。