Səhv baş verdikdə

Müştərilərə bankomatların işləməməsi halında nə etməli olduqlarını izah etmək üçün bankın tövsiyəsi, hər bir belə bankomatda qəzanın baş verməsi ilə bağlı bankın səmimi təəssüf və kədərini ifadə edən bir etiket yapışdırmaq idi. Həmin etiketi oxuyan müştəriyə ən yaxın işləyən bankomata (ümid edirik ki, o, fasiləsiz işləyir) getmək təklif olunurdu.

Bunun üçün bütün n bankomatların yerləşdiyi siyahı hazırlandı. Sizin vəzifəniz hər bir bankomat üçün ona ən yaxın olanını Evklid məsafəsindən istifadə edərək tapmaqdır.

Giriş məlumatları

Birinci sətir testlərin sayını t (t ≤ 15) ehtiva edir. Hər bir test bankomatların sayından n (2 ≤ n ≤ 10^5) başlayır. Növbəti n sətirin hər biri bir bankomatın x və y koordinatlarını ehtiva edir (0 ≤ x, y ≤ 10^9). Heç bir bankomatın koordinatları üst-üstə düşmür.

Çıxış məlumatları

Hər bir test üçün n sətir çıxış edin. i-ci sətir i-ci bankomatdan onun ən yaxın qonşusuna qədər olan məsafənin kvadratını ehtiva etməlidir.