幸运树

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Tom喜欢幸运数。我们都知道一个正整数是幸运数当且仅当其十进制表示形式只包含数字47.例如,数47,744,4是幸运的,而5,17,467不是。

    一天Tom邂逅了一棵有n个结点的树。另外,他发现,这棵树的是带权的,也即树的每条边都有一个权值(一个正整数)。只有当一条边的权值是幸运数时我们才说这条边是幸运的。大家可以注意到,一棵树是一个具有n个结点恰好有n-1条边的无向连通图。

      Tom想知道到存在多少顶点三元组(i,j,k)
满足从ij的路径上必须存在至少一条幸运边,同时满足从ik的路径上必须存在至少一条幸运边(三个顶点两两不相同)。三元组中的三个数顺序是有关的,顺序不同整体也是不同的,例如,三元组(1,2,3)不等于三元组(2,1,3),也不等于三元组(1,3,2)

   找出存在多少这样的顶点三元组。

Input

输入数据由多组,处理到文件结束。每组第一行是一个正整数n(1<=n<=50)——顶点的个数。接下来n-1行,每行三个数:Ui,Vi,Wi(1 < = Ui,Vi < = n, 1 < = Wi < = 10^9)——被一条边连接的两个顶点以及这条边的权值。

Output

    每组一行,仅有一个数,即要求的三元组的总个数。

Sample Input

4
1 2 4
3 1 2
1 4 7
4
1 2 4
1 3 47
1 4 7447

Sample Output

16
24

Hint


Source

tongjiantao