Khu du lịch gồm ~n~ điểm thăm quan (các điểm thăm quan đượ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 điểm thăm quan ~u_i~ với điểm thăm quan ~v_i~ và có độ dài ~c_i~. Bờm muốn đi thăm một số cặp điểm thăm quan bằng chiếc xe Yamaha Jupiter của mình. Bình xăng của chiếc xe này có thể chứa tối đa ~k~ lít xăng, để đi được 1 đơn vị độ dài thì chiếc xe sẽ tiêu thụ đúng 1 lít xăng. Bờm chỉ có thể đổ đầy lại bình xăng khi đang ở một trong ~n~ điểm thăm quan.

Yêu cầu: bạn hãy lập trình xử lý ~q~ câu hỏi của Bờm. Mỗi câu hỏi, Bờm sẽ cho trước hai điểm thăm quan ~s_i, t_i~ mà Bờm muốn đi. Bạn cần tính số lần ít nhất mà Bờm cần đổ đầy lại bình xăng nếu muốn di chuyển từ điểm thăm quan ~s_i~ đến thành phố ~t_i~ (bình xăng của xe đã đầy lúc xuất phát tại ~s_i~ nên không tính là một lần đổ). Nếu không tồn tại một lộ trình di chuyển hợp lệ thì in ra ~-1~.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên dương ~n, m, k~ (~1 \le n \le 300~; ~0 \le m \le \frac{n(n-1)}{2}~; ~1 \le k \le 10^9~);
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~u_i, v_i, c_i~ (~1 \le u_i, v_i \le n~; ~u_i \ne v_i~; ~1 \le c_i \le 10^9~);
• Dòng tiếp theo chứa một số nguyên dương ~q~ (~1 \le q \le n(n-1)~);
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~s_i, t_i~ (~1 \le s_i, t_i \le n~; ~s_i \ne t_i~).

Kết quả

Gồm ~q~ dòng là kết quả bạn tính được ứng với ~q~ câu hỏi của Bờm.

Ví dụ

Ví dụ 1

DOXANG.INP

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

DOXANG.OUT

0
1

Ví dụ 2

DOXANG.INP

4 0 1
1
2 1

DOXANG.OUT

-1

Giới hạn

• Subtask 1 (40% số test): ~1 \le n \le 100~;
• Subtask 2 (60% số test): ~100 < n \le 300~.