A. Сложный путь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стас живет в селе Аусомбург, административный центр которого представляет из себя треугольник. Для этого треугольника выполняется следующее:

  • его вершины находятся в целочисленных координатах,
  • координаты его вершин неотрицательные,
  • его вершины не лежат на одной прямой.

Стас называет точку на границе административного центра (то есть на границе треугольника) безопасной, если он может добраться до нее по прямой от хотя бы одной точки прямой $$$y = 0$$$, не пересекая внутренность административного центра.

На рисунке серым цветом изображен административный центр. Первый путь не является корректным, потому что он идет не по прямой. Второй путь не является корректным, потому что он пересекает внутренность административного центра. Третий и четвертый пути являются корректными.

Найдите суммарную длину небезопасных частей границы. Можно показать, что эти части являются отрезками и их количество конечно.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Описание каждого набора входных данных состоит из трех строк, в каждой из них находится два целых числа $$$x_i$$$, $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$) — координаты вершин административного центра.

Выходные данные

Для каждого набора входных данных выведите единственное вещественное число — ответ на задачу.

Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-9}$$$. Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}$$$.

Пример
Входные данные
5
8 10
10 4
6 2
4 6
0 1
4 2
14 1
11 2
13 2
0 0
4 0
2 4
0 1
1 1
0 0
Выходные данные
0.0000000
0
2.0000
0.00
1
Примечание

На рисунке изображены треугольники административных центров для первых трех наборов входных данных. Треугольники пронумерованы в соответствии с тем, к какому набору входных данных они относятся.

В первых двух наборах входных данных все точки на границах административных центрах являются безопасными, поэтому ответ $$$0$$$.

На рисунке ниже черным цветом отмечены небезопасные точки границы административного центра в третьем наборе входных данных:

В четвертом наборе входных данных также все точки границы административного центра являются безопасными.