CSG-CPC
Online Judge

1077 : 2019

         Time Limit: 5 Sec     Memory Limit: 512 Mb     Submitted: 111     Solved: 39    

Description

Bobo 有一棵 n 个点的树,点的编号是 1, 2, …, n. 树有 (n − 1) 条边,第 i 条边的端点是 aibi,权值是 ci. 求满足 u < v(u, v) 数量,满足点 u 到点 v 路径上的权值和是 2019 的倍数。

Input

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

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

接下来 (n − 1) 行,其中第 i 行包含三个整数 ai, bici.

  • n ≤ 2 × 104
  • 1 ≤ ai, bi ≤ n
  • 0 ≤ ci < 2019
  • n 的总和不超过 105.

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

Author

ftiasch