树上小鸟和路径

题面描述

校门口种了一颗新的树，小青爬上去一看，发现树上的每个边都写了一个数字。她觉得这棵树非常有意思，直到树上掉下来一只小鸟。小鸟问她，你知道树上路径的gcd的结果为x的路径有多少条？

当然，小鸟说的路径是简单路径，即：每条边只能走一次。

输入

第一行输入一个整数 $n$，代表节点个数。($1\leq n\leq 5\times 10^4$)

第二行到第 $n$ 行每行输入三个整数 $u,v,w$ ，代表 $u$ 与 $v$ 有一条边，边权是 $w$。($1\leq u,v\leq n$,$1\leq w\leq 10^9$)

第 $n+1$ 行一个整数 $k$ 。($1\leq k\leq 10^9$)

输出格式

一行一个整数，代表答案。

样例输入 #1

5
1 2 6
2 3 10
2 4 15
4 5 21
2

样例输出 #1

1

样例输入 #2

12
1 2 6
1 3 10
1 4 15
2 5 14
2 6 22
3 7 26
3 8 35
4 9 21
4 10 33
7 11 39
7 12 65
1

样例输出 #2

33