Given a tree on n
vertices (a connected undirected acyclic graph with n−1
edges), where each edge has a weight w
. Let's call a simple path of length k
increasing if there exists an integer x>=
2 such that the weight of the first edge of the path is divisible by x
, second edge — is divisible by x2
, ……, the weight k
th edge is divisible by x k
.
Find the maximum length k
increasing path where k
— the number of edges in it.
Input
The first line contains a single integer n
(1 <= n
<= 100000) - number of nodes in the tree.
The following n−1
lines contain three integers u
, v
, w
( 1<= v
<= n, 1<= w
<= n,  ;u ≠ v, 1 <= w
<= 107) - numbers of vertices connected by the next edge and its weight.< /p>
Output
Print a single integer k -
the maximum length of an ascending path.
Note
A simple path is a path such that all vertices in it are distinct.
In the 1st example, there is a path of length 2: 3 — 1 — 2. Then the appropriate x = 2
is suitable for it. It can be shown that there is no increasing path of greater length.
In the 2nd example, there is a path of length 3: 3 — 4 — 5 — 6. Then the appropriate x = 2
is suitable for it. It can be shown that there is no increasing path of greater length.
Examples
# |
Input |
Output |
1 |
4
1 2 8
1 3 6
1 4 3
|
2
|
2 |
6
1 2 2
2 3 4
3 4 2
4 5 4
5 6 8
|
3
|