Tý được bố mua cho một chiếc xe máy điện mới nên rất háo hức muốn tham quan một số địa điểm trong thành phố. Thành phố có N địa điểm tham quan đánh số từ 1 đến N và M con đường hai chiều nối giữa các địa điểm đó.

Sau khi tìm hiểu thêm về khoảng cách giữa các điểm tham quan đó, Tý và các bạn cùng có một câu hỏi giống nhau: một cái xe máy điện chạy với khoảng cách tối đa d Km (thì hết điện, sau khi đã xạc đầy), nếu xuất phát tại địa điểm i thì có bao nhiêu địa điểm khác nhau có thể đến tham quan bằng cái xe máy điện đó? Giả sử tại các địa điểm tham quan đều có thể xạc đầy điện cho xe để đi tiếp.

Biết sơ đồ các địa điểm tham quan trong thành phố và độ dài của các con đường, bạn hãy trả lời câu hỏi của Tý và các bạn Tý nhé.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương T là số bộ dữ liệu có trong tệp (1≤T≤3).

• 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, M, Q với N là số địa điểm, M là số đường nối hai chiều và Q là số câu hỏi (1 ≤ N ≤ 4000, 1 ≤ M ≤ 10000, 1 ≤ Q ≤ 80000).

  • M dòng tiếp theo mỗi dòng ghi ba số nguyên dươngx, y, lvới nghĩa là giữa hai địa điểm x, y có đường nối hai chiều có độ dài là l(1≤ x, y ≤N,1≤l≤ 10⁹).

  • Q dòng tiếp theo mỗi dòng ghi hai số nguyên dương i, d tương ứng với một câu hỏi (1 ≤ i ≤ N, 1 ≤ d ≤ 10⁹)

Kết quả: Tương ứng với một câu hỏi ghi ra một dòng gồm một số nguyên dương là số địa điểm khác nhau có thể tham quan.

Ví dụ:

Giới hạn:

• Có 40% số test có 1 ≤ N< 100, 1 ≤ M ≤ 1000, 1 ≤ Q ≤ 1000.

• Có 60% số test có1 ≤N ≤ 4000, 1 ≤ M ≤ 10000, 1 ≤ Q ≤ 80000.