Bobo 有一颗 $n$ 个点的树，点的编号是 $1, 2, \dots, n$. 树有 $(n - 1)$ 条边，第 $i$ 条边的端点是 $a_i$ 和 $b_i$，权值是 $c_i$. 求满足 $u < v$ 的 $(u, v)$ 数量，满足点 $u$ 到点 $v$ 路径上的权值和是 $2019$ 的倍数。

输入格式

输入文件包含多组数据，请处理到文件结束。

每组数据的第一行包含一个整数 $n$.

接下来 $(n - 1)$ 行，其中第 $i$ 行包含三个整数 $a_i$, $b_i$ 和 $c_i$.

• $n \leq 2 \times 10^4$
• $1 \leq a_i, b_i \leq n$
• $0 \leq c_i < 2019$
• $n$ 的总和不超过 $10^5$.

输出格式

对于每组数据，输出一个整数，表示所求的值。

样例输入

4
1 2 1
1 3 2018
1 4 1
4
1 2 0
1 3 0
1 4 0
3
1 2 1
2 3 1

样例输出

2
6
0