Description

Ming Ming encountered $n$ quadratic functions $S_i(x)= ax^2 + bx + c$ while doing homework. He whimsically designed a new function $F(x) = \max\{S_i(x)\}, i = 1\ldots n$.

Ming Ming now wants to find the minimum value of this function over the interval $[0,1000]$, accurate to four decimal places, rounded.

Input Format

The input contains $T$ test cases. The first line of each test case is an integer $n$;

The next $n$ lines each contain $3$ integers $a$, $b$, $c$, representing the coefficients of each quadratic function. Note: The quadratic function may degenerate into a linear one.

Output Format

For each test case, output one line representing the minimum value of the new function $F(x)$ over the interval $[0,1000]$. The result should be accurate to four decimal places, rounded.

Sample 1

2
1
2 0 0
2
2 0 0
2 -4 2

0.0000
0.5000

Data Range and Hints

For $50\%$ of the data, $1 \leq n \leq 100$;

For $100\%$ of the data, $1 \leq T \leq 10$, $1 \leq n \leq 10^5$, $0 \leq a \leq 100$, $0 \leq |b| \leq 5000$, $0 \leq |c| \leq 5000$.