eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Квадратная страна 5

Квадратная страна 5

Лимит времени 2 секунды
Лимит использования памяти 16 MiB

Первое арифметическое действие, которое учатся выполнять школьники Квадратной страны — это возведение в квадрат целых положительных чисел. На первом уроке школьникам предлагают только "удобные" числа, то есть числа, для возведения в квадрат которых достаточно дописать к ним спереди несколько цифр (например, 76 — удобное число, поскольку 76^2 = 5776). Конечно, числа не должны содержать ведущих нулей. Задание не должно быть слишком сложным, поэтому исходное число должно состоять не более чем из n цифр.

Сколько различных вариантов задания смогут подготовить учителя для первого урока?

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

В единственной строке записано целое число n (1n2000), максимальная длина числа, которое может быть предложено школьникам.

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

Выведите количество удобных для возведения в квадрат чисел, состоящих не более чем из n цифр.

Пример

Входные данные #1
1
Выходные данные #1
3
Автор Алексей Самсонов
Источник Ural SU Contest. Petrozavodsk Winter Session, February 2009