Задача E. Идеальная пара ≡

Условие

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

Формат входных данных

Единственная строка входного файла содержит натуральное число $n$.

$\textbf{Обратите внимание}$, что при заданных ограничениях для хранения ответа необходимо использовать $64$-битный тип данных, например $\textbf{long}$ $\textbf{long}$ в $\textbf{C++}$, $\textbf{int64}$ в $\textbf{Free}$ $\textbf{Pascal}$, $\textbf{long}$ в $\textbf{Java}$.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

$1 \le n \le 10^{12}$

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при $n \le 10^{5}$, получат не менее 40 баллов.

Пояснение к примерам

В первом примере дано $n = 1$. Проверим: $\frac{1 + 9}{2} = 5 \in N$ и $\sqrt {1 \times 9} = 3 \in N$. Числа, меньшие 9, не дают натуральных чисел для среднего арифметического или среднего геометрического одновременно (число 1 не подходит для пары, так как числа должны быть различны).

Во втором примере дано $n = 8$. Проверим: $\frac{8 + 2}{2} = 5 \in N$ и $\sqrt {8 \times 2} = 4 \in N$.

Примеры тестов

1

9

8

2