Cho \(N\) hang chuột (\(N \le 100\)) được đánh số từ \(1\) đến \(N\) và \(E\) là số thứ tự của "hang an toàn". Nếu trong khoảng thời gian \(T\) mà các con chuột có thể chạy từ hang \(1\) đến \(E\) thì con chuột đó an toàn.

Một số hang chuột thông nhau bởi đường đi một chiều. Ví dụ, tốn \(x\) đơn vị thời gian để chuột có thể chạy từ hang \(a\) đến hang \(b\).

Lưu ý:

• Đường đi là một chiều, trừ khi có mô tả về chiều ngược lại và thời gian cần thiết để đi mỗi chiều có thể khác nhau.
• Không có khái niệm "kẹt đường" trong bài tập này.

Đếm số lượng chuột có thể chạy đến "hang an toàn" sau \(T\) đơn vị thời gian.

Input:

Dòng đầu tiên là số bộ test. Sau đó là 1 dòng trống. Các bộ test cũng cách nhau bởi 1 dòng trống. Mỗi bộ test như sau:

• 3 dòng đầu tiên của mỗi bộ test lần lượt là 3 số: \(N\), \(E\), \(T\).
• Dòng thứ 4 của mỗi bộ test là số đường đi giữa các hang \(M\).
• \(M\) dòng tiếp theo của mỗi bộ test có dạng: \(a\) \(b\) \(x\) mô tả có đường đi một chiều từ hang \(a\) đến hang \(b\) và tốn \(x\) đơn vị thời gian để đi.

Output

• Với mỗi bộ test, output số lượng chuột có thể chạy đến "hang an toàn" sau \(T\) đơn vị thời gian.

Constraints

• \(n \le 100\)

Example

Sample input

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

Sample output

3