Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

B. Точки на плоскости
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть двумерная координатная плоскость, и вам надо расставить $$$n$$$ фишек на ней.

Вы можете ставить фишки только в точки с целочисленными координатами. Стоимость поставить фишку в точку $$$(x, y)$$$ равна $$$|x| + |y|$$$ (где $$$|a|$$$ означает абсолютное значение числа $$$a$$$).

Стоимость расстановки $$$n$$$ фишек равна максимуму из стоимостей каждой фишки.

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

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

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

В первой и единственной строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — количество фишек, которое вам нужно расставить.

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

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

Пример
Входные данные
4
1
3
5
975461057789971042
Выходные данные
0
1
2
987654321
Примечание

В первом наборе входных данных, вы можете разместить единственную фишку в точку $$$(0, 0)$$$ с общей стоимостью $$$0 + 0 = 0$$$.

Во втором наборе, вы можете, например, поставить фишки в точки $$$(-1, 0)$$$, $$$(0, 1)$$$ и $$$(1, 0)$$$ со стоимостями $$$|-1| + |0| = 1$$$, $$$|0| + |1| = 1$$$ и $$$|0| + |1| = 1$$$. Расстояние между каждой парой фишек больше чем $$$1$$$ (например, расстояние между $$$(-1, 0)$$$ и $$$(0, 1)$$$ равно $$$\sqrt{2}$$$). Общая стоимость равна $$$\max(1, 1, 1) = 1$$$.

В третьем наборе, вы можете, например, поставить фишки в точки $$$(-1, -1)$$$, $$$(-1, 1)$$$, $$$(1, 1)$$$, $$$(0, 0)$$$ и $$$(0, 2)$$$. Общая стоимость равна $$$\max(2, 2, 2, 0, 2) = 2$$$.