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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹²

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

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

Решения, верно работающие при n ≤ 10⁵, получат не менее 40 баллов.

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

В первом примере дано n = 1. Проверим: 1 + 92 = 5 ∈ N и √1 × 9 = 3 ∈ N. Числа, меньшие 9, не дают натуральных чисел для среднего арифметического или среднего геометрического одновременно (число 1 не подходит для пары, так как числа должны быть различны).

Во втором примере дано n = 8. Проверим: 8 + 22 = 5 ∈ N и √8 × 2 = 4 ∈ N.

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

1

9

8

2