1077 : 2019

Description

Bobo 有一棵 n 个点的树，点的编号是 1, 2, …, 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 ≤ 2 × 10⁴
• 1 ≤ a_i, b_i ≤ n
• 0 ≤ c_i < 2019
• n 的总和不超过 10⁵.

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