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

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

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