Almost Palindrome

Тавсифи масъала

A palindrome is a number whose digits read the same from left to right and from right to left. Examples: $7$, $121$, $4004$.

Palindrome checking is done as follows. Let the number have length $k$. Compare the first $\lfloor k/2 \rfloor$ digits with the last $\lfloor k/2 \rfloor$ digits in pairs:

• 1st digit $\leftrightarrow$ last digit,
• 2nd digit $\leftrightarrow$ second last digit,
• 3rd digit $\leftrightarrow$ third last digit,
• and so on.

Each such comparison is called a pair. If all pairs are equal, the number is a palindrome.

Almost palindrome

A number is called almost palindrome if, among all these pairs:

• exactly one pair has different digits (exactly 1 mismatching pair),
• all other pairs match.

So, palindromes themselves (with $0$ mismatching pairs) are not almost palindromes.

Given an integer $N$, count how many almost palindrome numbers are in the range from $1$ to $N$.

Input Format

One integer $N$ ($1 \le N \le 10^{18}$).

Output Format

Print one integer --- the number of almost palindrome integers in $[1,\, N]$.

Scoring

15

5