У вас есть двумерная координатная плоскость, и вам надо расставить \(n\) фишек на ней.
Вы можете ставить фишки только в точки с целочисленными координатами. Стоимость поставить фишку в точку \((x, y)\) равна \(|x| + |y|\) (где \(|a|\) означает абсолютное значение числа \(a\)).
Стоимость расстановки \(n\) фишек равна максимуму из стоимостей каждой фишки.
Вам нужно расставить \(n\) фишек на плоскости так, чтобы евклидово расстояние между любой парой фишек было строго больше \(1\) и стоимость расстановки была как можно меньше.
Выходные данные
Для каждого набора входных данных, выведите одно целое число — минимально возможную стоимость расстановки \(n\) фишек, если расстояние между каждой парой фишек должно быть строго больше \(1\).
Примечание
В первом наборе входных данных, вы можете разместить единственную фишку в точку \((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\).