Description

A palindromic number is an integer that reads the same when written normally and when written in reverse. For example, the numbers $142241$ and $102201$ are palindromic, but the numbers $1023401$ and $10510$ are not. You want to decompose a number $n$ into a sum of two palindromic numbers. Please compute the number of ways to decompose it in this form.

Input Format

Only one line contains an integer $n \ (1 \leq n \leq 10^{18})$.

Output Format

Output an integer representing the number of ways to decompose $n$ as the sum of two palindromic numbers.

156

4

9524

4

42657

6

5735832847451

28

Hint

In the first sample, the decompositions are: $(5, 151), (55, 101), (101, 55), (151, 5)$.

In the second sample, the decompositions are: $(515, 9009), (636, 8888), (8888, 636), (9009, 515)$.

In the third sample, the decompositions are: $(33, 42624), (333, 42324), (4884, 37773), (37773, 4884), (42324, 333), (42624, 33)$.

Translated by ChatGPT 5