题目描述

给出一棵树，边有边权，边权要么是 $1$，要么是 $2$。

有 $q$ 次询问，每次你想从 $x$ 走到 $y$，但每天至多只能走 $z$ 的距离。并且，每天走完后，你只能在树上的结点里停留。

至少要走几天？

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行每行三个正整数 $a,b,c$，表示树上有 $(a,b)$ 这条边，边权为 $c$。

接下来一行一个正整数 $q$。

接下来 $q$ 行每行三个正整数 $x,y,z$，表示一次询问。

输出格式

$q$ 行，每行一个非负整数，为询问的答案。

样例

输入

5
1 2 1
2 3 2
1 4 2
4 5 1
5
1 5 3
1 3 2
2 5 4
1 2 10
4 5 2

输出

1
2
1
1
1

数据范围

对于所有数据，$1\le n,q\le 10^5,1\le c\le 2,1\le z\le 2n,1\le a,b,x,y\le n$。