eolymp
bolt
Try our new interface for solving problems
Problems

Знову функція?

Знову функція?

Time limit 2 seconds
Memory limit 256 MiB

Козак Вус знову вигадав одну цікаву функцію!

Функція f(x, y) = \sqrt{(x-a)^2+(y-b)^2}+\sqrt{(x-c)^2+(y-d)^2}, де a, b, c, d — відомі коефіцієнти.

На цей раз Козаку Вусу цікаво знати мінімальне значення f(x, y). Допоможіть йому розв'язувати цю задачу.

Вам треба буде відповісти на q незалежних випадків.

Input data

У вхідних даних знаходяться кілька (не менш одного) тестових випадків.

Перший рядок містить одне ціле число q ( 1 \le q \le 10^5 ) — кількість тестових випадків.

Кожен з наступних q рядків містить по чотири цілі числа a, b, c і d (1 \le a, b, c, d \le 10^6).

Output data

Виведіть q рядків. i-ий рядок повинен містити відповідь на i-ий запит — мінімальне значення функції f(x, y).

Ваша відповідь буде вважатися правильною, якщо її абсолютна або відносна похибка не перевищує 10^{-4}.

Формально, нехай ваша відповідь дорівнює a, а відповідь журі дорівнює b. Ваша відповідь буде зарахована, тоді й тільки тоді, коли \frac {| a - b |} {\max {(1, | b |)}} \le 10 ^ {-4} .

Examples

Input example #1
3
1 1 10 4
3 8 1 14
113 97 257 457
Output example #1
9.486832981
6.324555320
387.731866114

Scoring

Гарантується, що рiшення, якi працюватимуть правильно при 1 \le q \le 1000 та 1 \le a, b, c, d \le 10, отримають принаймнi 40\% балiв.

Author Kostya Denisov