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 kth 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
|