Numbers

10^18 이하의 n이 주어질 때 a + b = n을 만족하는 순서 있는 팰린드롬 쌍 (a, b)의 개수를 구한다.

어려움8수학완전 탐색구현해시맵아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제 설명

예제4

문제

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

입력

There is only one line containing the integer n (1 ≤ n ≤ 1018).

출력

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

힌트

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).