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

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

For each test case print in a separate line the number of almost palindromes no greater than a.

Examples