The first arithmetical operation taught to the children of the Square country is the calculation of squares of positive integers. At the first lesson the children are provided with “easy” numbers, calculating a square of which can be done by writing a few digits in front of them (i.e. 76 is an easy number because 762 = 5776). Of course, the numbers cannot contain leading zeroes. The task shouldn't be too difficult, so the easy numbers shouldn't contain more than n digits. How many different easy numbers can teachers prepare for the first lesson?
The only input line contains an integer n (1 ≤ n ≤ 2000), the maximal length of the easy number the children can be provided with.
Output the number of different easy numbers consisting of at most n digits.
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009