1077 : 2019

Description

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

Input

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

每组数据的第一行包含一个整数 \(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\).

Output

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

Sample

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

Hint

Source

Author

ftiasch