Since the days of yore alchemy has been studied and practiced. The practice makes alchemists able to transmute materials into other forms. Transmuting materials requires drawing a transmutation circle on the ground. A little known fact about transmutation circles is they can be drawn inside other transmutation circles. By activating certain configurations in the correct order, more powerful transmutations can be produced. Activating circles incorrectly can have drastic effects on the alchemist's body.

A young alchemist named Nicholas Flamel would like to learn the ways of alchemy. He has drawn several configurations of transmutation circles on the ground. When a circle is activated it burns bright red representing the element of fire. The activation itself produces no extra energy. The secret is when an outer transmutation circle is activated. When this occurs, all already active circles in the area of the activated circle quickly change to their respective complement elements. Fire changes to a cool blue representing water. Circles that were blue for water will burn fiery red once again. This change can either create or drain energy from the transmutation. Beware, energy can go negative at any time by temporarily draining the alchemist's life force (but the spell continues to work just fine).

Nicholas wants to get as much out of his transmutations as possible. To do so requires him to activate all his circles in an order that releases the most energy. Determine the maximum amount of energy that can be released.

Input

Starts with a single line with the number of test cases t between 1 and 100 inclusive. For each set of transmutation circles there will be a line with a number n (1 ≤ n ≤ 2000). This represents the number of transmutation circles. The next n lines contain spaced-separated integers x y a b. The first three integers represent the coordinates and radius of the circle, while the last two represent the energy release for going from fire to water (A), and water to fire (B) (-10000 ≤ x, y ≤ 10000, 1 ≤ r ≤ 10000, -500 ≤ a, b ≤ 500).

No two circles will intersect or touch.

Output

For each set of transmutation circles print a single integer representing the maximum energy that can be produced by activating the circles. On the following line print the permutation of the input circles that can produce that energy. If multiple permutations exist, print the one that comes first lexicographically.