Perfect Squares
Very hard
Execution time limit is 1 second
Runtime memory usage limit is 64 megabytes
Given a natural number N (where 0 ≤ N ≤ 100), determine how many natural numbers with exactly N digits are perfect squares.
Input
The input consists of a single natural number N.
Output
Print the number of N-digit natural numbers that are perfect squares.
Examples
Input #1
Answer #1
Submissions 666
Acceptance rate 3%