Background

Special for beginners, ^_^

Description

徐老师一家人出门自驾游了。

有 $N（1<N\le300）$ 个城市，之间有 $M$ 条道路，第 $i$ 条道路连接城市 $A_i$ 和 $B_i$ ， 长度为 $C_i$ 公里，任何两座城市之间至多只有一条道路。

徐老师的车的油箱加满后可以行驶 $L（\le10^9）$ 公里。只有城市里面有加油站，

假设出发时油箱是满的，问从城市 $s_i$ 到 $t_i$ 中途需要加油至少几次，如果无法到达目的地，则输出 -1 。

Format

Input

第一行三个非负整数 $N、M、L$，分别表示城市数、道路数、满油箱能行驶的公里数。

接下来 $M$ 行，每行三个正整数 $A_i、B_i、C_i$ ，表示从城市 $A_i$ 到 $B_i$ 的双向道路的长度为 $C_i$ 公里。

然后一个正整数 $Q$ 表示接下来的询问数，保证没有重复的询问。

最后 $Q$ 行，每行两个正整数 $s_i、t_i$ ，表示问从城市 $s_i$ 到 $t_i$ 中途需要加油至少几次。

Output

输出 $Q$ 行，每行对应一个询问的答案，即加油次数，-1表示无法到达目的地。

Samples

6 5 10
1 2 5
2 3 6
3 4 9
4 5 5
5 6 5
1
1 4

2

Limitation

1s, 1024KiB for each test case.