当前没有测试数据。

题目描述

精彩纷呈的沙漠越野赛就要开始了，比赛将在在浩瀚的沙漠中举行。

沙漠中分布着 $N$ 个补给站（编号为 $1 \sim N$）。各补给站之间通过 $M$ 条沙漠公路相连，每条公路均为双向通行。第 $i$ 条公路连接补给站 $U_i$ 和补给站 $V_i$，路程为 $C_i$ 公里。

参赛选手驾驶着越野车穿越沙漠，越野车的油箱容量为 $L$ 升，行驶 $1$ 公里需要消耗 $1$ 升燃油。每当探险队到达某个补给站时，他们可以选择：

• 在补给站将油箱加满。
• 不加油，直接前往下一个补给站。

现有 $Q$ 个赛程，第 $j$ 个赛程从指定的补给站 $S_j$ 出发前往目标补给站 $T_j$。选手如果在行驶过程中因燃油耗尽而中途熄火，则当前赛程挑战失败（不影响下一个赛程的挑战），退出比赛。选手从指定的补给站出发时，他的容量为 $L$ 的油箱已加满。

请问对于每个赛程，选手如果想要挑战成功，从补给站 $S_j$ 到补给站 $T_j$ 中途至少需要补充多少次燃油（不含出发时加满的一箱油）？

输入格式

第 $1$ 行输入三个整数 $N, M, L$。

接下来 $M$ 行，每行输入三个整数 $U_i, V_i, C_i$。

下一行读入整数 $Q$。

接下来 $Q$ 行，每行输入两个整数 $S_j, T_j$。

输出格式

输出 $Q$ 行，每行输出一个整数。第 $j$ 行的数字表示从补给站 $S_j$ 到 $T_j$ 的赛程中，选手至少需要补给燃油的次数，如果无论如何都无法抵达目的地，则输出 $-1$。

样例 #1

输入

3 2 5
1 2 3
2 3 3
2
3 2
1 3

输出

0
1

数据范围

对于 $100\%$ 的数据，满足 $2 \le N \le 300$，$0 \le M \le \frac{N(N-1)}{2}$，$1 \le L \le 10^9$，$1 \le U_i, V_i \le N$ 且 $U_i \neq V_i$，每一对 $U_i, V_i$ 均不重复（即无重边），$1 \le C_i \le 10^9$，$1 \le Q \le N(N-1)$，$1 \le S_j, T_j \le N$ 且 $S_j \neq T_j$。