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