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 76² = 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.