ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Winter 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Square Country 5

Time limit: 2.0 second
Memory limit: 64 MB
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?

Input

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

Output the number of different easy numbers consisting of at most n digits.

Sample

inputoutput
1
3
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009
To submit the solution for this problem go to the Problem set: 1698. Square Country 5