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