Hasinur's Mission!

Let me tell you something about Hasinur:

1. He is a religious person. He prays 5 times a day.
2. He loves math.
3. He loves prime numbers.
4. He loves to travel.

Hasinur travels a lot. When he visits a city, he goes through every mosque of that particular city and prays.

In January 2020, he had a chance to visit a city in India called Sikkim. After reaching Sikkim, his first target was to visit all the mosques situated in Sikkim. Hasinur collected a map where he found the location of all the mosques located at Sikkim and the roads that connect them. It is guaranteed that he can go to any mosque from any other mosque using only one single path. A path consists of one or more roads.

There are n mosques in the city of Sikkim. All the mosques are connected by a total of (n - 1) roads. The roads are bi-directional and have a number associated with it. Hasinur knows the location of all the mosque, he knows the number of all the roads and the path between every mosque in that city.

Hasinur likes prime numbers as well. So he wants to know how many combinations of (X, Y, Z) of mosques are there where he would be able to visit at least one road associated with a prime number along the way while going from X to Y and also from X to Z. Here, mosque X ≠ mosque Y ≠ mosque Z.

Input

The first line will contain n (2 ≤ n ≤106), the number of mosques in Sikkim.
Next (n - 1) lines each will contain 3 numbers: a, b, and c (1 ≤ a, b ≤ n; a ≠ b; 1 ≤ c ≤ 106), denoting there is a road between a and b, and c is the number associated with that particular road.

Output

Output a single integer denoting the answer.

Samples

Input	Output
7 1 2 1 2 7 7 2 5 12 1 4 15 1 3 7 3 6 10	94
The first few of possible combinations are (1,7,3) , (1,3,7), (1,7,6), (2,3,7) and so on. Figure: The map of city 'Sikkim' according to the sample input. The green marked roads are the road associated wiht a prime number.

Input	Output
4 1 3 2 1 2 5 1 4 20	16
The possible combinations are: (3,4,2), (2,3,1), (3,1,4) (1, 2, 3), (4,3,2), (2,4,1), (3,2,1), (3,4,1) (2,1,3), (1,3,2), (2,1,4), (4,2,3), (2,3,4), (2,4,3), (3,1,2), (3,2,4). Figure: The map according to the sample input/output.

Dataset is huge. Use faster I/O methods.