Найближчі точки#12873

Найближчі точки

2 seconds
256 megabytes
Medium

Вам дано попарно різних точок (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n), кожна з яких лежить на одній з осей та (тобто, для кожного принаймні одне з чисел x_i та y_i = 0).

Для кожної точки знайдіть відстань до найближчої точки до неї. Іншими словами, для кожного знайдіть мінімальне значення \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} по всім j \neq i.

Input

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

Перший рядок кожного набору вхідних даних містить одне ціле число (2 \le n \le 2\cdot 10^5)  — кількість точок.

-ий з наступних рядків містить два цілих числа x_i, y_i (-10^9 \le x_i, y_i \le 10^9, принаймні одне з чисел x_i та y_i рівне нулю)  — координати -ої точки.

Гарантується, що всі точки попарно різні (тобто для кожних i \neq j виконується принаймні одне з x_i \neq x_j, y_i \neq y_j).

Гарантується, що сума по всім наборам вхідних даних не перевищує 2\cdot 10^5.

Output

Для кожного набору вхідних даних виведіть чисел, -те з яких рівне відстані від -ої точки до найближчої точки до неї.

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

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

Examples

Example 1

Loading
Loading

Note

В першому наборі вхідних даних, найближча точка до точки  — точка , а до точки  — точка .

В другому наборі вхідних даних, точки , , , (в цьому порядку) формують квадрат зі стороною 10\sqrt{2}, тому для кожної точки найближча до неї точка знаходиться на відстані 10\sqrt{2}.

В третьому наборі вхідних даних, точка найближча до точок . Для точки же однаково близько точки та .