eolymp
bolt
Try our new interface for solving problems
Problems

Танцы с баобабами

Танцы с баобабами

Time limit 3 seconds
Memory limit 256 MiB

Шаман танцев Никитэофль ведёт за собой вереницу танцующих соплеменников, морально подгатавливая их к участию в интеллектуальном ритуале "эрудит-квартетль".

Начиная из точки с координатами (0, 0), Никитэофль ведёт вереницу на север, постепенно поворачивая на восток, проходя по часовой стрелке четверть окружности радиуса 1. Затем он продолжает, проходя по часовой стрелке четверть окружности радиуса 2, далее аналогично радиуса 3, 4 и т.д. (см. рисунок).

В прерии, где происходит вышеописанный танец, растут n баобабов. Для каждого баобаба определите, какое минимальное расстояние от него до танцующей вереницы, в предположении, что танец будет продолжаться бесконечно.

Input data

В первой строке входного файла содержится натуральное число n, не превышающее 100000. В каждой из следующих n строк содержаться по два вещественных числа x_i и y_i, не превышающие 10^6 по абсолютной величине - координаты баобабов (ось x направлена на восток, ось y - на север). Все координаты даны не более чем с тремя знаками после запятой.

Выведите n строк - расстояния от баобабов до танцующей вереницы, с абсолютной или относительной точностью до 10^{-6}.

Examples

Input example #1
5
0 0
3 2
-1 -1
-4 5
3 4
Output example #1
0.000000000000
1.605551275464
1.414213562373
1.928932188135
0.614835192865