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

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

Функція $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

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

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

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

Output

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

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

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

Examples

Scoring

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