Tại đảo này, có ~N~ điểm thiện nguyện được đánh số từ 1 đến ~N~ và có ~P~ con đường hai chiều nối giữa các địa điểm thiện nguyện đó.

Sau khi nghiên cứu địa hình và phân tích rõ khoảng cách giữa các điểm thiện nguyện trên đảo, Đoàn thiện nguyện đưa ra giả thiết:

Với chiếc ô tô đã đổ đầy nhiên liệu (xăng), chạy được với khoảng cách tối đa ~S~ km. Vậy, nếu cũng chiếc ô tô đó, Đoàn sẽ xuất phát tại địa điểm ~K~ thì có bao nhiêu điểm khác nhau mà Đoàn sẽ đi qua? Giả sử tại các điểm thiện nguyện trên đảo, ô tô sẽ được đổ đầy nhiên liệu để tiếp tục đi.

Yêu cầu: Bạn hãy giúp đưa ra kết quả chính xác.

Dữ liệu

• Dòng đầu tiên ghi số nguyên dương ~T~ là số bộ dữ liệu có trong file;
• Tiếp theo là ~T~ bộ dữ liệu, mỗi bộ bao gồm:
  • Dòng thứ nhất ghi ba số nguyên dương ~N, P, U~ với ~N~ là số điểm thiện nguyện, ~P~ là số đường nối hai chiều và ~U~ là số giả thiết đưa ra;
  • ~P~ dòng tiếp theo, mỗi dòng ghi ba số nguyên dương ~x, y, z~ (với hai địa điểm ~x, y~ có đường nối hai chiều có độ dài ~z~; ~1 \le x, y \le N~, ~1 \le z \le 10^9~);
  • ~U~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~K, S~ tương ứng với một giả thiết (~1 \le K \le N~, ~1 \le S \le 10^9~).

Kết quả

Tương ứng với ~T~ bộ dữ liệu, mỗi bộ dữ liệu là ~U~ dòng, dòng thứ ~i~ là số điểm khác nhau (kể cả điểm xuất phát ~K~) mà Đoàn có thể đi qua trong giả thiết thứ ~i~.

Ví dụ

HELP.INP

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

HELP.OUT

2
4
2

Giải thích:

• Giả thiết 1: Nếu ô tô xuất phát từ điểm 3 và đi được tối đa 2 km thì chỉ có thể đến điểm 2. (Đáp án: 2 điểm)
• Giả thiết 2: Nếu ô tô xuất phát từ điểm 2 và đi được tối đa 4 km thì có thể đi từ 2 sang 3. Sau đó, từ 3 quay lại 2, rồi đi tiếp sang 1 và 4. Vậy số điểm khác nhau mà Đoàn đã đi qua là 4.
• Giả thiết 3: Nếu ô tô xuất phát từ điểm 2 và đi được tối đa 2 km thì Đoàn có thể đi từ điểm 2 sang điểm 3.

Đồ thị của ví dụ: các đường 1-2 (độ dài 3), 2-3 (độ dài 2), 3-1 (độ dài 5), 4-1 (độ dài 3).

Giới hạn

• Có 60% số test có ~1 \le N \le 10^2~, ~1 \le P \le 10^3~, ~1 \le U \le 10^4~, ~T = 1~;
• Có 40% số test có ~1 \le N \le 5 \times 10^3~, ~1 \le P \le 10^4~, ~1 \le U < 5 \times 10^4~, ~T \le 3~.