Integral of All Horrors
In response to the 2010 Deep Horizon oil spill, ACME Inc. develops a machine that uses a high-tech particle beam to remotely seal oil leaks. To test the prototype, ACME has built a underwater test bed with n independent oil leaks that are named L_1, L_2, ..., L_n.
Each leak L_i (1 ≤ i ≤ n) is characterized by parameters r_i and t_i. r_i is the initial oil leakage rate in litres per second (L/s). While L_i is being sealed by the particle beam, the leakage rate would linearly decrease, and reach 0 L/s (i.e. become sealed) after t_i seconds of continual operation.
For example, let L_1 be characterized by r_1 = 20 and t_1 = 4. Initially oil spew at a rate of 20 L/s. After 1 second of sealing, the rate reduces to 15 L/s; after 2 seconds, the rate is 10 L/s; after 3 s, we have 5 L/s; and after 4 s the leak is sealed. Throughout these 4 seconds, the total volume of oil that leak from L_1 is 20 (L/s) × 4 (s) / 2 = 40 L (area of a triangle). Meanwhile, other leaks continue to spew oil, and are unaffected until the particle beam is directed at them.
You are responsible for demonstrating the machine. At t = 0, you activate the beam to seal leaks. The particle beam takes negligible time to target a leak, and is never idle. Therefore every leak is sealed at t = t_1 + t_2 + ... + t_n (and then everyone applauds). However, a lot of oil would be leaked during the test. The precise amount depends how you choose to target the particle beam throughout the demonstration.
Given parameters for L_1, L_2, ..., L_n, your task is to minimize total volume (in litres) of oil leakage between t = 0 (particle turned on) and t = t_1 + t_2 + ... + t_n (all leaks sealed). Note that there are multiple test cases (all independent from one another).
Input
The first input line contains the number of test cases N, 1 ≤ N ≤ 50.
Each test case begins with a single line containing an integer n. Each of the following n lines specifies L_i (for 1 ≤ i ≤ n) with two integers r_i and t_i, separated by space.
n is the total number of oil leaks, and satisfies 1 ≤ n ≤ 50.
r_i is the initial leakage rate (in L/s) of L_i, and satisfies 1 ≤ r_i ≤ 500.
t_i is the total beam time (in s) to seal L_i, and satisfies 1 ≤ t_i ≤ 500.
Output
For each test case, print the minimum possible total volume oil spilled during the test (in L), to 2 decimal places.