Square Country 5#4349
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. — is an easy number because 76^2 = 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 digits.
How many different easy numbers can teachers prepare for the first lesson?
The only input line contains an integer (1 \leq n \leq 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 digits.
Example 1