Prime Minister Bodi is visiting Amardesh. He is willing to go to all the notable places of Khakha city. For that reason he want go through all the roads in Khakha at least once while he travels from one place to another. The people of Amardesh is very irritated with this as all the roads are blocked when Prime Minister Bodi is traveling to ensure his security, and the people has to suffer for that. So the Government has decided to let Bodi travel each road only once and build some flyovers, which connects two notable places, so that he can complete his visit to all the notable places while going through every road in Khakha city. Bodi can start his journey at any place and end at any place you select. Please note, all roads are flyovers are bi-directional. You are given this task to minimize the cost of building flyovers for Bodi to complete his journey. The cost to build a flyover is the square of the Euclidean distance between two notable points. You can assume that all the notable places are already connected with each other. Input Input will start with number of test cases, T (T ≤ 1000). Following that will be the number of notable places, N (0 < N ≤ 15). Following N lines contain two integers, X and Y (0 ≤ X, Y ≤ 1000) as the coordinate for each place. After that will be the number of roads, M (0 < M ≤ 1000). Following M lines will contain two integers, A and B, denoting there exists a road between the notable places A and B. Notable places are numbered in the sequence they are given in the input, starting with 0. Output For each test case, print one line of output, ‘Case X: Y ’. Where X is the test case number and Y is the minimum cost to build the flyover(s). Sample Input 2 3 00 01 10 3 01 12 20 4 00 01 10 11 4 02 23 32 13
2/2 Sample Output Case 1: 0 Case 2: 1