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

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

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

1. 在补给站将油箱加满。

2. 不加油，直接前往下一个补给站。

现有 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 条公路连接如下：

• 公路 1：连接补给站 1 与补给站 2，路程为 3 公里。
• 公路 2：连接补给站 2 与补给站 3，路程为 3 公里。

越野车油箱容量为 5 升，每公里耗油 1 升，起始时加满燃油。

• 对于从补给站 3 到补给站 2 的赛程：选手可直接沿公路从补给站 3 驶向补给站 2，耗油 3 升，油箱加满足以抵达，中途无需补给，因此输出 0。
• 对于从补给站 1 到补给站 3 的赛程：选手先从补给站 1 驶向补给站 2（耗油 3 升），到达补给站 2 时剩余 2 升油，但前往补给站 3 所需耗油为 3 升，因此必须在补给站 2 补给一次，将油箱加满后才能继续行驶，故输出 1。

数据范围

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