Almost palindromes#1313
Sign in

Almost palindromes

1 second
122.174 megabytes
Hard

We call a number almost a palindrome if its decimal notation can be turned into a palindrome by changing no more than one digit. For example, numbers , , and are almost palindromes, but or are not.

Given a number , find the number of such integers that 1 \leq x \leq a and is almost a palindrome.

Input

Contains several test cases. Each test case gives the number (1 \leq a \leq 10^{18}). The last line contains and is not processed.

Output

For each test case, print in a separate line the number of almost palindromes not exceeding .

Examples

Example 1

Loading
Loading