How Big Is It?

Time limit1sMemory limit128 MB

Summary

Given up to 8 circles, arrange them all touching the bottom of a box to minimize the box's total width.

Level: Medium7 of 10
Topics: Backtracking, Geometry, Brute force
Solved: No attempts yet

Problem

Ian is going to California, and he has to pack his things, including his collection of circles. Given a set of circles, your program must find the smallest rectangular box in which they fit.

All circles must touch the bottom of the box. The figure below shows an acceptable packing for a set of circles (although it may not be the optimal packing for those particular circles). Note that in an ideal packing, each circle should touch at least one other circle.

An acceptable packing of circles resting along the bottom of a box

Input

The first line contains a single positive integer $n$ ( $n \le 100$ ), the number of data lines that follow. Each of the next $n$ lines describes one packing problem: it starts with a positive integer $m$ ( $m \le 8$ ), the number of circles on that line, followed by the $m$ radii of those circles. The radii need not be integers.

Output

For each data line (that is, every line except the first), output the width of the smallest box that can pack that line's circles. Print each answer on its own line, with exactly three digits after the decimal point. Do not print a leading zero unless the value is less than 1 (for example, 0.543).

Examples2

Example 1

Input

3
3 2.0 1.0 2.0
4 2.0 2.0 2.0 2.0
3 2.0 1.0 4.0

Expected output

9.657
16.000
12.657

Example 2
Input
```
1
1 3.5
```
Expected output
```
7.000
```