It’s believed that frogs jump due to lack of natural physical de- fense against predators. However, there are some types of frogs that do not leap. In this problem, we will consider a hybrid ver- sion of a frog that can both leap and walk. Consider a magical creek with N stones. The shape of each stone is either a circle or a square. Our frog is currently standing on stone 1 and it is going to make (N −1) leaps so that it can land on every stone. It is believed that after making N − 1 jumps, the frog will grow wings and fly away. After every jump, it loses 10% ot its ‘leaping energy’. That means in the K-th leap it can jump to a maximum distance of L ∗ 0.9k−1, where L is the initial maximum jump distance. The frog, however, can walk from any point to any other point within a stone without loss of any energy. In this problem, you have to find the minimum value of L that will enable the frog to visit all the stones starting from stone 1. Obviously, the visiting order of the stones will be such that the value of L is minimized. When calculating the distances, assume the frog is a point and the stones are circles and squares on a 2D Cartesian coordinate. Input The first line of input is an integer T (T ≤ 200) that indicates the number of test cases. Each case starts with a line containing an integer N (2 ≤ N ≤ 15) that represents the number of stones. The next N lines contain the descriptions of the stones starting from stone 1. Each stone will be given in the format ‘type X Y R’. type can be ‘C’ or ‘S’ and represents circle and square respectively. If type is equal to ‘C’, then (X, Y ) will give you the center of the circle and R will give you the radius. If type is ‘S’, then (X, Y ) will give you the lower left corner of the square and R will give the length of the sides. The sides of the squares are axis parallel. 0 ≤ X, Y ≤ 1000000, 0 < R ≤ 1000 and stones will be non-overlapping. Output For each case, output the minimum value of L. Errors less than 10−6 will be ignored. Note: For the second sample we have the picture below. Initial value of L is 5.555556. First, the frog makes a leap to stone 3. It loses 10% of energy and that means the next leap distance can be at most 5.555556 * 0.9 = 5.000000. Since the shortest distance between stone 3 and stone 2 is 5.000000, the next leap will enable the frog to land safely on stone 2. Sample Input 2 2 C005
2/2 C 10 0 2 3 C002 S 10 1 4 S312 Sample Output 3.000000 5.555556