Given a tree with N vertices and N-1 undirected edges, where each edge has a weight associated with it.

gcd(A,B) is gcd of weight of all the edges in the path from A to B.

len(A,B) is number of edges in path from A to B.

You have to maximise gcd(A,B) * len(A,B) over all possible pairs A,B.

Input

N - number of nodes

Next N-1 lines contains 3 integers a,b,c representing there is an edge between a and b of weight c.

Output

In a single line print the maximum value.

Constraints

1<=T<=10

2 <= N <= 100000

c <= 100000

Sample Input

1

3

1 2 10

2 3 4

Sample output

10