Отже, обожнювач звуку Вова вирішив віддати на доопрацювання свою апаратуру. Одним із способів покращити звучання - використати навісний монтаж провідниками більшого поперечного перерізу, також для ще більшого зменшення опору вони повинні бути по можливості якомога коротшими. Як з'єднати 2 виводи зрозуміло, також нескладно шукається оптимальний монтаж, який з'єднує 3 контакти. А ось 4?

На друкованій платі є 4 контакти, які потрібно з'єднати між собою (між кожною парою контактів повинен бути контакт). Дозволяється додати від 0 до 3 допоміжних контактів. А також з'єднувати контакти між собою відрізками провідника. Мета — мінімізувати сумарну довжину провідників.

Вхідні дані

Перший рядок містить кількість тестів n (1 ≤ n ≤ 100). Кожний тест складається з 4 рядків, що містять (xi, yi) координати контактів (-200 ≤ xi, yi ≤ 200, 1 ≤ i ≤ 4). Жодні дві точки з чотирьох не співпадають. Тести розділені між собою порожнім рядком.

Вихідні дані

Для кожного тесту вивести в окремому рядку мінімально можливу довжину провідника. Число потрібно вивести з не менше ніж 4 десятковими цифрами.