Treeland 有 $n$ 座城市，由双向道路连接。从任意城市出发都可以到达其他任何城市，且路径唯一。换句话说，Treeland 的道路网络构成了一棵树。

你正在计划一次环绕 Treeland 的公路旅行。你的车油箱容量为 $c$ 升。对于每条道路，你知道通过它所需的燃油量。你可以在任何城市加油，但城市之间没有加油站。由于 Treeland 的燃油价格便宜，你只想尽量减少加油次数，以便有更多时间欣赏 Treeland 的风景。

你还不确定要走哪条路线。请回答 $q$ 个查询：给定两个城市 $u$ 和 $v$，从城市 $u$ 到城市 $v$ 需要加油多少次？假设你从城市 $u$ 出发时油箱是满的。

输入格式

第一行包含测试用例的数量 $Z$ ($1 \le Z \le 10\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n, q$ 和 $c$ ($2 \le n \le 200\,000, 1 \le q \le 200\,000, 1 \le c \le 10^9$)，分别表示城市数量、查询数量和油箱容量。

接下来的 $n - 1$ 行描述道路网络。每行包含整数 $a_i, b_i$ 和 $w_i$ ($a_i \neq b_i, 1 \le a_i, b_i \le n, 1 \le w_i \le c$)，表示第 $i$ 条道路连接的两个端点城市以及所需的燃油量。

最后 $q$ 行描述查询。每行包含两个不同的整数 $u_j$ 和 $v_j$ ($u_j \neq v_j, 1 \le u_j, v_j \le n$)，表示查询的城市对。

所有测试用例的 $n$ 之和不超过 $400\,000$。所有测试用例的 $q$ 之和不超过 $400\,000$。

输出格式

对于每个查询，输出一行，包含最少可能的加油次数。

样例

样例输入 1

1
7 6 5
1 2 3
2 3 3
2 4 1
1 5 2
5 6 1
6 7 4
3 6
3 7
4 6
4 7
3 4
7 1

样例输出 1

2
2
1
2
0
1

说明

对于样例中的第一个查询，其中一条最优路线如下：

• 从城市 3 出发，油箱加满 5 升燃油；
• 行驶至城市 2，消耗 3 升燃油，油箱剩余 2 升；
• 给车加油，使油箱再次达到 5 升；
• 行驶至城市 1，消耗 3 升燃油，油箱剩余 2 升；
• 行驶至城市 5，消耗剩余的 2 升燃油；
• 最后一次给车加油；
• 行驶至城市 6，在 5 升燃油中仅消耗 1 升。