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.

Yêu cầu: Với mỗi câu hỏi, hãy xác định số lượng địa điểm khác nhau có thể đến tham quan từ địa điểm xuất phát với khoảng cách tối đa ~d~.

Input

• Dòng đầu tiên ghi số nguyên dương ~T~ là số bộ dữ liệu (~1 \le T \le 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~ (~1 \le N \le 4000, 1 \le M \le 10000, 1 \le Q \le 80000~).
  • ~M~ dòng tiếp theo, mỗi dòng ghi ba số nguyên dương ~x, y, l~ (~1 \le x, y \le N, 1 \le l \le 10^9~), nghĩa là giữa hai địa điểm ~x, y~ có đường nối hai chiều độ dài ~l~.
  • ~Q~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~i, d~ (~1 \le i \le N, 1 \le d \le 10^9~).

Output

• Với mỗi 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.

Sample Input 1

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

Sample Output 1

3
1