Задача №3202. Магия числа 23

Олимпиада завершена. Режим дорешивания.

По заданному числу \(N\) найдите натуральное число \(K\), такое что:

  • число \(\overline{KK}\) (повторённая два раза десятичная запись \(K\)) является точным квадратом некоторого натурального числа (см. примеры),
  • \(K\) при записи в десятичной системе счисления имеет длину от \(N\) до \(N+23\) (включительно).

Так, для \(N=1\) условию удовлетворяет, например, число \(K=13223140496\), т.к. оно имеет длину 11, что укладывается в диапазон от 1 до 24, а также число \(1322314049613223140496\) является точным квадратом натурального числа.

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

Вводится одно натуральное число \(N\) (\(1 \le N \le 2323\)).

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

Выведите искомое число \(K\). Если чисел, удовлетворяющих условию, несколько, выведите любое из них. Если таких чисел не существует, выведите 0.

Примечания

Тесты состоят из четырёх групп. В этой задаче нет off-line групп. Баллы за каждую группу начисляются только при прохождении всех тестов этой группы.

  1. Тесты 1--4, из условия, оцениваются в 0 баллов.
  2. Тест 5, \(N = 13\), оценивается в 30 баллов.
  3. Тесты 6--14. В них \(N \le 80\). Группа оценивается в 30 баллов.
  4. Тесты 15--29. Полные ограничения, оценивается в 40 баллов.
Примеры
Входные данные
1
Выходные данные
13223140496
Входные данные
11
Выходные данные
13223140496
Входные данные
10
Выходные данные
13223140496
Входные данные
39
Выходные данные
1322314049586776859504132231404958677685950413223140496
Сдать: для сдачи задач необходимо войти в систему