Kamome on erittäin kiinnostunut meteorien havaitsemisesta. Hän loi äärettömän suuren kaksiulotteisen mallin, joka simuloi meteorien liikettä (vaikka se ei oikeastaan simuloikaan yhtään mitään). Tässä simulaatiossa on $n$ meteorimallia, ja $i$. meteorimallin paino on $m_i$. Jokainen meteorimalli liikkuu vakionopeudella pitkin kiinteää suoraa (se voi myös olla paikallaan).

On kulunut pitkä aika siitä, kun Kamome käynnisti tämän mallin. Eräänä päivänä Kamome sai äkillisen idean ja otti kaksi valokuvaa nykyisestä mallista. Kun Kamomen sijainti valitaan origoksi, jokaisessa valokuvassa $i$ ($i = 1, 2$) $j$. meteorimalli sijaitsi tason pisteessä $(x_{i,j}, y_{i,j})$.

Voit laskea kunkin meteorimallin lentoradan, mutta se ei riitä! Kamome haluaa sinun laskevan jokaiselle meteorimallille $i$ suurimman gravitaatiovoiman, jonka mikä tahansa muu meteorimalli kohdistaa siihen koko sinä aikana, kun malli on ollut käynnissä (voit ajatella tämän äärettömän pitkänä aikana ennen valokuvien ottamista ja sen jälkeen).

Huomaa, että tavallinen gravitaatiokaava voidaan kirjoittaa muodossa $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$. Jotta vältyttäisiin joidenkin reunatapausten käsittelyltä, Kamome antaakin sinulle syötteenä luvut $m'_i = \frac{1}{m_i}$, ja sinun tarvitsee vain tulostaa tulos, joka saadaan jakamalla vastaus $G$:llä ja ottamalla siitä käänteisluku. Toisin sanoen laske jokaiselle $i$ arvo $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$, missä $D_t(i, j)$ on meteorimallien $i$ ja $j$ välinen etäisyys ajanhetkellä $t$, ja $t$ voi olla mikä tahansa reaaliluku (negatiivinen, positiivinen tai nolla).

Syöte

Jokainen testi sisältää useita testitapauksia. Ensimmäinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 10^4$), joka ilmoittaa testitapausten lukumäärän. Seuraavaksi on testitapausten kuvaus.

Ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($2 \le n, \sum n \le 10^5$), joka ilmoittaa meteorimallien lukumäärän.

Toinen rivi sisältää $n$ kokonaislukua $m'_i$ ($1 \le m'_i \le 100$), joiden määritelmä on kerrottu yllä.

Seuraavat $n$ riviä sisältävät kukin neljä kokonaislukua $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ ($-10^8 \le x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i} \le 10^8$, $0 \le |x_{1,i} - x_{2,i}|, |y_{1,i} - y_{2,i}| \le 5$), jotka ilmoittavat $i$. meteorimallin sijainnin näissä kahdessa valokuvassa.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää $n$ reaalilukua yllä määritellyllä tavalla.

Oletetaan, että sinun vastauksesi on $x$ ja tuomariston vastaus on $y$; vastauksesi katsotaan oikeaksi jos ja vain jos $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$.

Esimerkit

Syöte 1

2
2
1 2
0 0 1 0
1 1 0 1
3
1 2 3
1 0 0 -1
-1 0 0 1
0 1 1 0

Tuloste 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Huomautus

Ensimmäisessä testitapauksessa meteorimallin 1 ja meteorimallin 2 välinen suurin gravitaatiovoima saavutetaan, kun ne saapuvat pisteisiin $(0.5, 0)$ ja $(0.5, 1)$. Tällöin vastaus on $m'_1 m'_2 d_{\min}^2 = 2$.