Employees at Endurance have decided to go for a expedition. You are to organise the expedition. After satisfying the remaining costs of the trip, you are left with budget D.

There are N cities available to visit and these cities are connected by m one-way roads. Each road i has length some length and cost to be paid to travel along that road, associated with it.

Initially you will start from city 1. Now, you will try to pose some queries and try to answer them to select the cities for expedition.

Each query will be of type a, b where a is the city which you wanna travel to and b is the budget in which you want to travel. For each query you have to tell the minimum distance traveled by you to reach that city within budget b. If it is not possible to reach within the budget b, print -1 as ans.

INPUT
First line of input contains a single integer t denoting number of test cases.
First line of each test case start with 3 integers n, m, D where n is the number of cities, m is number of roads and D is the maximum budget that you have.
Next m lines contains 4 integers u, v, c, l where u, v denotes that there is one way road from city u to city v, c is the cost associated with that road and l is the length of the road.
Next line contains a single integer q denoting number of queries.
q line follows each having 2 integers a, b where a is the destination city and b is the budget within which you want to reach a.

OUTPUT
For each query output single line containing minimum distance to be traveled if you can reach that city within that budget else -1.

NOTE: There will only be atmost 1 direct road between any two cities.
Use Fast I/O.

Constraints
1<=t<=5
1<=n<=500
n-1<=m<=min(2000, n*(n-1)/2)
1<=D<=1000
1<=u, v, a<=n
1<=b<=D
1<=length of any road<=100000
1<=cost of any road<=500
1 <=q<= $10^5$

Setter : Karan Thakkar