Palindrome Numbers

Interview

Time limit1sMemory limit1024 MB

Summary

Given n below 10^10, count the palindrome numbers from 1 to n inclusive.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

For a positive integer $P$ , if the digits of $P$ read from left to right are the same as the digits read from right to left, $P$ is called a palindrome number. For example, $1$ , $101$ , and $12322321$ are all palindrome numbers. Given a positive integer $n$ , write a program that prints the number of distinct palindrome numbers less than or equal to $n$ . For example, when $n = 20$ , there are 10 palindrome numbers up to 20 ( $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ , $9$ , $11$ ).

Input

The input is read from standard input. The first line contains a positive integer $n$ ( $1 ≤ n < 10^{10}$ ).

Output

The output is written to standard output. Print the number of distinct palindrome numbers less than or equal to $n$ on one line.

Examples2

Example 1
Input
```
20
```
Expected output
```
10
```
Example 2
Input
```
101
```
Expected output
```
19
```