In a magical forest, there are $n$ villages connected by $n-1$ roads, forming a tree. Each road has a positive integer representing its magical power.

A traveler can journey between any two distinct villages along their unique simple path. The power of a journey is defined as the greatest common divisor (GCD) of the powers of all roads along the path.

The forest guardian has chosen a special integer $k$. A journey is considered enchanted if its power is not divisible by $k$.

Your task is to count the number of enchanted journeys.

Journeys between the same two villages are counted only once, regardless of direction.

Input

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le 10^9$).

Each of the next $n-1$ lines contains three integers $u$, $v$, and $w$ ($1 \le u,v \le n$, $u \ne v$, $1 \le w \le 10^9$), describing a road between villages $u$ and $v$ with magical power $w$.

It is guaranteed that the roads form a tree.

Output

Print a single integer: the number of enchanted journeys.

Example

stdin

5 6
1 2 6
2 3 10
2 4 12
4 5 3

stdout

7

Note

Here $k = 6$. The tree has the roads $1 - 2$ (power $6$), $2 - 3$ (power $10$), $2 - 4$ (power $12$) and $4 - 5$ (power $3$).

The $7$ enchanted journeys are:

• $1 \to 3$ (path $1 - 2 - 3$): $\gcd(6, 10) = 2$;
• $1 \to 5$ (path $1 - 2 - 4 - 5$): $\gcd(6, 12, 3) = 3$;
• $2 \to 3$ (path $2 - 3$): $\gcd(10) = 10$;
• $2 \to 5$ (path $2 - 4 - 5$): $\gcd(12, 3) = 3$;
• $3 \to 4$ (path $3 - 2 - 4$): $\gcd(10, 12) = 2$;
• $3 \to 5$ (path $3 - 2 - 4 - 5$): $\gcd(10, 12, 3) = 1$;
• $4 \to 5$ (path $4 - 5$): $\gcd(3) = 3$.

None of these powers is divisible by $6$.

The remaining $3$ journeys are not enchanted, because their power is divisible by $6$:

• $1 \to 2$: $\gcd(6) = 6$;
• $1 \to 4$ (path $1 - 2 - 4$): $\gcd(6, 12) = 6$;
• $2 \to 4$: $\gcd(12) = 12$.