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 sau khi sạc đầy có thể chạy với khoảng cách tối đa \(d\) km thì hết điện, 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ể sạ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é!

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) là số bộ dữ liệu \((1\leq T\leq3)\);
• Tiếp theo là \(T\) bộ dữ liệu, mỗi bộ bao gồm:
  • Dòng thứ nhất ghi \(3\) số nguyên dương \(N,\ M,\ Q\) - lần lượt là số địa điểm tham quan, số con đường hai chiều và số câu hỏi truy vấn \((1\leq N\leq 4000,\ 1\leq M\leq10000,\ 1\leq Q\leq80000)\);
  • \(M\) dòng tiếp theo, mỗi dòng ghi \(3\) số nguyên dương \(x,\ y,\ l\) với ý nghĩa là giữa hai điểm \(x,\ y\) có đường nối hai chiều có độ dài là \(l\ (1\leq x,\ y\leq N,\ 1\leq l\leq10^9)\);
  • \(Q\) dòng tiếp theo, mỗi dòng ghi \(2\) số nguyên dương \(i,\ d\) tương ứng với một câu hỏi truy vấn \((1\leq i\leq N,\ 1\leq d\leq10^9)\).

Output

• Đáp án cho mỗi câu hỏi truy vấn được in ra trên 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ụ

Sample input

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

Sample output

3
1

Ràng buộc

• Có \(50\%\) số test tương ứng với \(50\%\) số điểm bài toán có \(1\leq N\leq100,\ 1\leq M\leq1000,\ 1\leq Q\leq1000\);
• Có \(50\%\) số test khác tương ứng với số điểm còn lại của bài toán không có ràng buộc gì thêm.