 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
First qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  2 seconds 

Memory limit  256 megabytes 
Maxim is playing a video game. It has n levels, numbered from 1 to n. Levels can be completed in any order, it takes Maxim a_{i} seconds to complete the ith level.
Maxim can find a magic artifact at one of the levels. There is exactly one magic artifact in the game, and once found it will increase the speed of Maxim's hero and reduce the time needed to complete the level. However, it is not known where the artifact is, the probability that it is at the ith level is p_{i}. The time needed to complete the ith level after the artifact is found is b_{i} second (b_{i} ≤ a_{i}). Note that artifact doesn't reduce the time needed to complete the level where it is found.
Maxim wants to choose the order he completes the levels, to minimize the expected time to complete the game. Help him to find the minimal possible expected time. Maxim must choose the order to complete the levels before playing the game, the order must not depend on whether the artifact was found or not at some level.
Recall that the expectation of a random variable is the sum over all possible outcomes of a product of the probability of such outcome and the value of the variable. In this problem the outcome corresponds to the level where the artifact is, and the value is the total time needed if the artifact is at that level.
Input format 
Input data contains several test cases. The first line contains t — the number of test cases (1 ≤ t ≤ 1000). Each test case is described in the following way: the first line contains integer n — the number of levels (1 ≤ n ≤ 10^{5}). The following n lines describe levels. Each level is specified with three integers a_{i}, b_{i} and x_{i} — the time to complete the level before the artifact was found, the time to complete it after the artifact was found, and the value that helps to find the probability to find the artifact at that level. The probability is calculated using the formula p_{i} = x_{i} / 10^{7} (1 ≤ b_{i} ≤ a_{i} ≤ 10^{5}; 0 ≤ x_{i} ≤ 10^{7}; the sum of all x_{i} is 10^{7}). The sum of values of n in all test cases of one input data is at most 5·10^{5}. 

Output format 
For each test case output one floating point value — the expected time to complete the game if the optimal order was chosen. The answer must have an absolute or relative error of at most 10^{  6}. 
Examples 
Input data
2 3 10 5 10000000 5 3 0 7 3 0 4 3 1 2500000 4 1 2500000 10 1 2500000 2 1 2500000
Output data
16 10.25 
