Given a tree with $n$ nodes, each edge is labeled with a lowercase letter.

Let $str(x,y)$ denote the string formed by the characters on the simple path from $x$ to $y$ in the tree.

A string $T$ is defined as "excellent" if and only if $T$ can be represented in the form $SS$, where $S$ is any non-empty string.

Calculate the number of distinct excellent strings that exist in the tree.

Input

The first line contains a positive integer $n$ ($2 \leq n \leq 5 \times 10^4$), representing the number of nodes in the tree.

The next $n-1$ lines each contain $x, y, c$, representing an edge connecting $(x, y)$ with the lowercase letter $c$ on it.

Output

Output a non-negative integer representing the answer.

Examples

Input 1

5
1 2 a
2 3 a
3 4 b
4 5 b

Output 1

2