Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

G. Optimizations From Chelsu
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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 1un.

You need to find the maximum value of len(u,v)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 (1t104) — the number of test cases. This is followed by their description.

The first line of each test case contains the number n (2n105) — the number of vertices in the tree.

The next n1 lines specify the edges in the format u, v, w (1u,vn, 1w1012).

It is guaranteed that the sum of n over all test cases does not exceed 105.

Output

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

Example
Input
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