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. 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). 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.