Numbers

Time limit1sMemory limit512 MB

Summary

Given n up to 10^18, count the ordered pairs of palindromes (a, b) whose sum is n.

Level: Hard9 of 10
Topics: Dynamic programming, Math, Brute force
Solved: No attempts yet

Input

A palindrome is an integer which reads the same backward as forward. For example, numbers 142241 and 102201 are palindromes, but 1023401 and 10510 are not. You want to represent a number $n$ as the sum of two palindromes. Find the number of ways to do it.

Input

There is only one line containing the integer $n$ ( $1 \le n \le 10^{18}$ ).

Output

Output one number, the number of ways to represent the number $n$ as the sum of two palindromes.

Hint

In the first test, the following pairs of numbers are suitable: $(5, 151)$ , $(55, 101)$ , $(101, 55)$ , $(151, 5)$ .

In the second test, the following pairs of numbers are suitable: $(515, 9009)$ , $(636, 8888)$ , $(8888, 636)$ , $(9009, 515)$ .

In the third test, the following pairs of numbers are suitable: $(33, 42624)$ , $(333, 42324)$ , $(4884, 37773)$ , $(37773, 4884)$ , $(42324, 333)$ , $(42624, 33)$ .

Examples4

Example 1
Input
```
156
```
Expected output
```
4
```
Example 2
Input
```
9524
```
Expected output
```
4
```
Example 3
Input
```
42657
```
Expected output
```
6
```
Example 4
Input
```
5735832847451
```
Expected output
```
28
```