Once again, people of Gigaland are unhappy because of political unrest between Broken Arrow and Shadow Coder. This time Broken Arrow wants to be in one step ahead of Shadow Coder in terms of war strategy. He wants to send his army to the battlefield from Megaland as soon as possible. For strategic reason, Broken Arrow wants to send at least K unit of army to the battlefield. The country of Gigaland consist of N cities (including Megaland and the battlefield) numbered from 1 to N and M unidirectional road. If Broken Arrow wants to send an army troop from city Ui to Vi using road i, the army troop will need Di days to reach city Vi starting from Ui and at most Wi armies can start their journey on each day from city Ui to go through the road i. As a great programmer of Gigaland, it is your duty to help Broken Arrow to find the minimum number of days required to send at least K armies from Megaland (city 1) to the battlefield (city N). Input Input starts with an integer, T (T ≤ 15) denoting the number of test cases. Each test case starts with threeintegers,N(2≤N≤50),M(1≤M≤N∗N)andK(1≤K≤100000). Eachofthenext M lines contain four integers Ui, Vi, Di and Wi (1 ≤ Ui,Vi ≤ N, Ui ̸= Vi, 1 ≤ Di,Wi ≤ 100000), description of road i. There will always be a path from Megaland to the battlefield and also there can be multiple paths. Output For each test case, print the test case number, starting from 1, and the minimum possible days required to send at least K armies from city 1 to city N. If the answer is more than 100 then print ‘-1’. Sample Input 2 334 1215 2326 1 3 5 10 339 1215 2326 1 3 5 10 Sample Output Case 1: 3 Case 2: 4