Đất nước Byteland có \(N\) thành phố (được đánh số từ \(1\) đến \(N\)) và \(M\) con đường hai chiều kết nối chúng với nhau. Con đường thứ \(i\) kết nối thành phố \(u_i\) với thành phố \(v_i\) và có độ dài \(c_i\). Oanh Trúc Béo muốn đi thăm thú một số cặp thành phố bằng chiếc xe Yamaha Grande của cô ấy. Bình xăng của chiếc xe này có thể chứa tối đa \(L\) lít xăng, và ở mỗi đơn vị độ dài thì chiếc xe sẽ tiêu thụ đúng \(1\) lít xăng. Cô ấy chỉ có thể đổ đầy lại bình xăng khi đang ở một trong \(N\) thành phố của Byteland (cũng đồng nghĩa với việc chiếc xe Grande này không thể hết xăng khi đang đi giữa một con đường nào đó).

Bạn hãy lập trình xử lý \(Q\) truy vấn. Mỗi truy vấn cho trước hai số nguyên \(s_i\), \(t_i\) và yêu cầu bạn tính số lần ít nhất Oanh Trúc Béo cần đổ đầy lại bình xăng nếu muốn di chuyển từ thành phố \(s_i\) đến thành phố \(t_i\) (bình xăng của cô ấy đã đầy sẵn lúc xuất phát tại \(s_i\) nên bạn không cần tính vào). Nếu không tồn tại một lộ trình di chuyển hợp lệ thì in ra \(-1\).

Input

• Dòng đầu chứa ba số nguyên \(N\), \(M\) và \(L\) (\(2\leq N\leq 300\), \(0\leq M\leq \dfrac{N(N-1)}{2}\), \(1\leq L\leq 10^9\)).

• Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa ba số nguyên \(u_i\), \(v_i\) và \(c_i\) (\(u_i\neq v_i\), \(1\leq c_i\leq 10^9\)). Dữ liệu đảm bảo mỗi cặp thành phố được nối với nhau bởi tối đa một con đường.

• Dòng tiếp theo chứa số nguyên dương \(Q\) (\(1\leq Q\leq N(N-1)\)).

• Dòng thứ \(i\) trong \(Q\) dòng tiếp theo chứa hai số nguyên \(s_i\) và \(t_i\) (\(s_i \neq t_i\)).

Output

• In ra \(Q\) dòng là câu trả lời tương ứng cho từng truy vấn.

Example

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

0
1

4 0 1
1
2 1

-1

5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0