The news has just arrived: The princess has been kidnapped by the monster. The prince became worried. But the chief scientist informed that the princess has a tracking device hidden in her locket and from that it is known that the princess is kept in a tower in a very big lake at Bermuda Triangle. The prince went out to save his princess and reached the lake. At the area it is not safe to fly so the prince needs to use a boat to reach the tower. The only problem is the big circular rocks in the lake which the prince cannot pass through. There are several of them in the lake. The prince has a satellite image of the area where the rocks are marked. The prince wondered what the shortest distance is between his current position and the tower. Can you help him? Input The first line of input will be the number of test cases T (T < 51). Then T cases will follow from the next line. Each case starts with 4 integers xp, yp, xt, yt. Here (xp,yp) is the position of the prince and (xt, yt) is the position of the tower. The next line will contain an integer n, number of rocks in the lake. Each of the following n lines will contain 3 integers xi, yi, ri. (xi, yi) is the center and ri is the radius of the i-th rock. The positions (xp,yp) and (xt,yt) will be different and both have positive distance from every rock. Output For each case first output one line in the format ‘Case k: d’, where k is the case number starting from 1 and d is the minimum distance the prince has to cover to reach the tower. See sample input and output for details. Note: • All positions are given in Cartesian coordinates system and all the distances are Euclidian dis- tances. • You may consider prince, his boat and the tower each as a point object. • The rocks will not overlap, but may touch each other. In this case, the prince cannot go through the touching point. • n will be between 0 and 50 inclusive. • All the coordinate will have an absolute value less than 1001. All the radii will be positive and less than 1001. • It is confirmed that the prince can reach the tower. • The output will be considered correct, if it has an absolute error less than 1e − 5. Sample Input 2 -3 2 2 -2 2 002
2/2 0 -5 3 -3 0 4 0 2 054 0 -3 3 Sample Output Case 1: 8.14159265 Case 2: 7.00000000