Primo is a famous guitar player in the city of Caracas, he wants to live his life at the fullest, so he went to the nearest food store to buy an arepa, a famous dish of all South America.

While eating his arepa, Primo received a call from his friend Maxx, who was piloting his helicopter when he soon noticed that a lot of fans were around the streets, pursuing and looking for Primo.

Primo is starting to go crazy, he wants to eat his arepa as many time he can before the fans takes him... He is not interested in the fans because he already has a girlfriend!

So, your task is very simple, Maxx (in his helicopter) will give you the connection between the streets, the time you can spend from street to street, and the amount of time the street has left before the fans takes it.

If some fans “take” a street, that street will be discarded, Primo won't go there... NOT EVEN DEAD!

Primo really likes arepas, so help him find the maximum time he can spend eating the food before the fans can reach him.

Input

Input will start with a number T of test cases, then, T cases will follow:

Each test case will start with 3 numbers N, R, M, corresponding, to number of intersections, number of streets and maximum time he can eat the arepa

Then, R lines will follow.

Each line will contain 3 numbers and a string Ri, Rj, Wij, Tij, corresponding to, Intersection I is connected to intersection J with a length of Wij minutes and the fans will arrive to the street in Tij minutes (or may not arrive, in this case, Tij will be equal to INF)

The final line of each test case will contain two numbers S, E corresponding to the starting intersection Primo is in (the food store) and the E will correspond to his house.

Note that: if the fans won't arrive to the street the Tij of the street will be INF.

Also note that: if you can go from the i-th intersection to the j-th intersection as you can go from the j-th intersection to the i-th intersection.

Output

Your output will start with a “Case #i: “ string, where I is the i-th case you are on.

If Primo can escape, you should output “Primo can escape in T minute(s)” where T Is the maximum amount of time he can spend eating his arepa, else, you should print “Primo can't escape”

Example

Input:
4
3 2 100
0 1 30 40
1 2 10 40
0 2
3 2 100
0 1 30 INF
1 2 10 INF
0 2
4 3 100
0 1 20 INF
1 2 40 INF
2 3 50 120
0 3
2 1 100
0 1 1 2
0 1

Output:
Case #1: Primo can't escape
Case #2: Primo can escape in 100 minute(s)
Case #3: Primo can escape in 9 minute(s)
Case #4: Primo can't escape

Constraints

1 ≤ N ≤ 100,000

1 ≤ R ≤ 100,000

1 ≤ M ≤ 100,000

0 ≤ R1, R2, S, E < N

1 ≤ Tij, Wij ≤ 500

Clarification: It is guaranteed that every intersection will be connected to at least one other intersection, there will be no equal relation on the input data and Primo will always reach his house.