有 N 个城市，编号从 1 到 N，以及 M 条道路。第 i 条道路连接城市 A_i 和城市 B_i，双向通行，长度为 C_i 单位。

你的车辆油箱最多可以容纳 L 升燃料，每行驶 1 单位距离消耗 1 升燃料。当你到达一个城市时，可以选择把油箱加满（也可以选择不加）；如果油箱在行驶途中用完燃料，就无法继续行驶。

你需要处理 Q 个询问：出发时油箱是满的，从城市 s_i 到城市 t_i，最少需要加多少次油？如果 t_i 不可达，输出 -1。

第一行三个整数 N, M, L。

接下来 M 行，每行三个整数 A_i, B_i, C_i，表示一条长度为 C_i 的双向道路。

接下来一行一个整数 Q。

接下来 Q 行，每行两个整数 s_i, t_i。

输出 Q 行，每行一个整数表示最少加油次数；不可达输出 -1。

样例解释

N=3,\ M=2,\ L=5，两条路 1-2 长 3、2-3 长 3。

• 3 \to 2 只要走 3 的距离，3 \le 5，不用加油，答案 0；

• 1 \to 3 全程 6，一箱油 5 不够，中途在城市 2 加一次油，答案 1。

数据范围

• 对于 20\% 的数据，1 \le N, M \le 10；

• 对于 50\% 的数据，1 \le N \le 80；

• 对于 100\% 的数据，1 \le N \le 300，0 \le M \le \frac{N(N-1)}{2}，1 \le L, C_i \le 10^9，1 \le Q \le N(N-1)，s_i \ne t_i，没有重边。

本题共 10 个测试点，每个 10 分。