Once upon a time, in Kingdom Monkey Kong, there was a brave and smart man called Prince Andrew. He loved to go for an adventure. He was always eager to found out interesting, thrilling, and magical experience.
One day, Prince Andrew went to Arribean Desert. After a few days of traveling, he entered a strange cave. Suddenly, the entrance cave is blocked. After that, there were lights gleaming inside the cave. Soon after that, there were sounds saying these words:

"Greetings, Prince Andrew. Welcome to the magical labyrinth. Right now you are in the first room of the labyrinth. In order to exit this cave, you have to collect the maximum coins you can get in here. Each room has different values of coins. Once you enter a room, you cannot go back to the previous room. If you fail to get the maximum coins, you will be trapped here forever. Now I am going to give you the route map of this labyrinth. Please proceed immediately to the next room. You will be able to leave this maze immediately after you have collected the maximum coins you can get. "

After hearing the mysterious voice, he thought of a strategy to finish the maze. He finally escaped from there, thanks to his brilliant mind. Now, can you figure it out how many coins exactly that he has taken so that he can escape from the magical labyrinth?

Input

Input starts with an integer T (1 ≤ T ≤ 10), denoting the number of test cases. Then, each test case is followed by an integer n (1 ≤ N ≤ 550) , the number of rooms in the labyrinth. The next line consists of n integers denoting the coins in the first room to the last room (0 ≤ number of coins in a room ≤ 10^9) . The next line of input consists of an integer m denoting the number of paths available from one room to another, followed by m lines consisting 2 integers, A and B, which is shows the path that connects room A to room B(1 ≤ A,B ≤ N). It is guaranteed that every path is unique and not bidirectional (you can go to room A to room B, but not to room B to A) and no cycle path will be formed(example A to B, B to C , C back to A). Every path is a valid path as well. Prince Andrew always starts from the first room.

Output

For each case print "Case X: E", where X (1 ≤ X ≤ T) is the case number, and E is the maximum coins he can take with the rules given above, followed by a newline.

Example

Input:
3
3
1 2 3
2
1 2
2 3
7
1 2 3 4 5 6 7
6
1 2
1 3
2 4
3 5
4 6
5 6
3
1 2 2
2
1 2
1 3

Output:
Case 1: 6
Case 2: 15
Case 3: 3

Note: You can see on the second testcase that there might be rooms that are unreachable. Multiple exits may exist (see test case 3 for example).

---

hide comments

	nadstratosfer: 2018-11-16 23:14:23 I think there's something wrong with the testfiles. My solution keeps crashing when trying to process T cases; reading till EOF gives WA instead.