In response to the \textbf{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 \textbf{n} independent oil leaks that are named \textbf{L_1}, \textbf{L_2}, ..., \textbf{L_n}. Each leak \textbf{L_i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{n}) is characterized by parameters \textbf{r_i} and \textbf{t_i}. \textbf{r_i} is the initial oil leakage rate in litres per second (\textbf{L/s}). While \textbf{L_i} is being sealed by the particle beam, the leakage rate would linearly decrease, and reach \textbf{0} \textbf{L/s} (i.e. become sealed) after \textbf{t_i} seconds of continual operation. For example, let \textbf{L_1} be characterized by \textbf{r_1 = 20} and \textbf{t_1 = 4}. Initially oil spew at a rate of \textbf{20 L/s}. After \textbf{1} second of sealing, the rate reduces to \textbf{15 L/s}; after \textbf{2} seconds, the rate is \textbf{10 L/s}; after \textbf{3 s}, we have \textbf{5 L/s}; and after \textbf{4 s} the leak is sealed. Throughout these \textbf{4} seconds, the total volume of oil that leak from \textbf{L_1} is \textbf{20} (\textbf{L/s}) × \textbf{4} (\textbf{s})\textbf{ / 2 = 40} \textbf{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 \textbf{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 \textbf{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 \textbf{L_1}, \textbf{L_2}, ..., \textbf{L_n}, your task is to minimize total volume (in litres) of oil leakage between \textbf{t = 0} (particle turned on) and \textbf{t = t_1 + t_2 + ... + t_n} (all leaks sealed). Note that there are multiple test cases (all independent from one another). \InputFile The first input line contains the number of test cases \textbf{N}, \textbf{1} ≤ \textbf{N} ≤ \textbf{50}. Each test case begins with a single line containing an integer \textbf{n}. Each of the following \textbf{n} lines specifies \textbf{L_i} (for \textbf{1} ≤ \textbf{i} ≤ \textbf{n}) with two integers \textbf{r_i} and \textbf{t_i}, separated by space. \begin{itemize} \item \textbf{n} is the total number of oil leaks, and satisfies \textbf{1} ≤ \textbf{n} ≤ \textbf{50}. \item \textbf{r_i} is the initial leakage rate (in \textbf{L/s}) of \textbf{L_i}, and satisfies \textbf{1} ≤ \textbf{r_i} ≤ \textbf{500}. \item \textbf{t_i} is the total beam time (in \textbf{s}) to seal \textbf{L_i}, and satisfies \textbf{1} ≤ \textbf{t_i} ≤ \textbf{500}. \end{itemize} \OutputFile For each test case, print the minimum possible total volume oil spilled during the test (in \textbf{L}), to \textbf{2} decimal places.