Baking bread is my favourite sparetime pursuit. I have a
number of stainless steel mixing bowls with straight sides, a
circular bottom and a wider circular top opening.
Geometrically, my bowls are truncated circular cones and for
this problem, the thickness of the metal may be
disregarded.
I store these bowls stacked in the natural way, that is with
a common vertical axis, and I stack them in an order that
minimises the total height of the stack. Finding this minimum
is the purpose of your program.
Input
On the first line of the input is a positive integer,
telling the number of test cases to follow (at most
$10$). Each case starts
with one line containing an integer $n$, the number of bowls ($2\leq n \leq 9$). The following
$n$ lines each contain
three positive integers $h, r,
R$, specifying the height, the bottom radius and the top
radius of the bowl, and $r<R$ holds true. You may also
assume that $h,r,R<1000$.
Output
For each test case, output one line containing the minimal
stack height, truncated to an integer (note:
truncated, not rounded).
Sample Input 1 
Sample Output 1 
2
2
60 20 30
40 10 50
3
50 30 80
35 25 70
40 10 90

70
55
