Пахом стоит в точке S и хочет как можно скорее добраться в точку T, чтобы там купить себе землю. Однако он увидел овраг, представляющий собой ломаную ABC. Какой минимальный путь придётся преодолеть Пахому, если он не хочет провалиться в овраг?

В первой строке записано количество тестов n (1 ≤ n ≤ 5000). В каждой из следующих n строк описывается один тест. Каждый тест представляет собой 10 целых чисел, записанных через пробел: x_S, y_S, x_T, y_T, x_A, y_A, x_B, y_B, x_C, y_C, являющихся координатами точек S, T, A, B и C соответственно. Все точки в тесте различны. Точки S и T не принадлежат ломаной ABC. Все координаты не превосходят по модулю 10.

Для каждого теста выведите ответ в отдельной строке, с точностью не менее 10⁻⁶.