Problems
Almost palindromes
Almost palindromes
We call number x almost a palindrome if its decimal notation can be turned into a palindrome changing no more than one digit. For example, numbers 1234321, 1234311 and 123421 are almost palindromic, and 1234213 or 12345331 are not.
Given number a, find the number of such integers x, that 1 ≤ x ≤ a and x is almost a palindrome.
Input data
Contains several test cases. Each test case gives the number a (1 ≤ a ≤ 10^18
). The last line contains 0 and is not processed.
Output data
For each test case print in a separate line the number of almost palindromes no greater than a.
Examples
Input example #1
10 1000 1000000 0
Output example #1
10 1000 45010