Bələdçilər
Vova, səs avadanlığını təkmilləşdirmək üçün yeni bir addım atmağa qərar verdi. Səs keyfiyyətini artırmağın bir yolu, daha böyük kəsik sahəsinə malik keçiricilərdən istifadə etməkdir. Bununla yanaşı, keçiricilərin müqavimətini azaltmaq üçün onların mümkün qədər qısa olması vacibdir. 2 çıxışı birləşdirmək asandır, 3 kontaktı birləşdirmək də çox çətin deyil. Bəs 4 kontaktı necə birləşdirmək olar?
Çap lövhəsində bir-biri ilə birləşdirilməli olan 4 kontakt var və hər bir kontakt cütü arasında əlaqə qurulmalıdır. 0-dan 3-ə qədər köməkçi kontakt əlavə etmək mümkündür. Kontaktları bir-biri ilə keçirici parçalar vasitəsilə birləşdirmək olar. Məqsəd, keçiricilərin ümumi uzunluğunu minimuma endirməkdir.
Giriş məlumatları
Birinci sətir testlərin sayını n (1 ≤ n ≤ 100) göstərir. Hər bir test 4 sətirdən ibarətdir və burada (x[i], y[i]) kontaktların koordinatları (-200 ≤ x[i], y[i] ≤ 200, 1 ≤ i ≤ 4) verilir. Dörd nöqtədən heç biri üst-üstə düşmür. Testlər arasında boş sətir var.
Çıxış məlumatları
Hər bir test üçün keçiricinin minimal mümkün uzunluğunu ayrıca sətirdə çıxarın. Rəqəm ən azı 4 onluq rəqəmlə göstərilməlidir.