eolymp
bolt
Try our new interface for solving problems
Problems

Almost palindromes

Almost palindromes

Time limit 1 second
Memory limit 122 MiB

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 1xa and x is almost a palindrome.

Input data

Contains several test cases. Each test case gives the number a (1a10^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