Problem B
Bowlstack

Baking bread is my favourite spare-time 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.

Figure 1: Illustrations of the two sample cases

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).

2
2
60 20 30
40 10 50
3
50 30 80
35 25 70
40 10 90

70
55