만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

숫자

시간 제한1초메모리 제한512 MB

요약
n이 주어질 때 a + b = n을 만족하는 회문 쌍 (a, b)의 개수를 구합니다.
난이도

어려움10점 중 9점

유형
동적 계획법, 수학, 완전 탐색
정답자
아직 제출이 없습니다

입력

회문은 앞으로 읽으나 뒤로 읽으나 같은 정수이다. 예를 들어 142241과 102201은 회문이지만, 1023401과 10510은 회문이 아니다. 정수 nn을 두 회문의 합으로 나타내는 방법의 수를 구하라.

입력

정수 nn이 한 줄에 주어진다 (1≤n≤10181 \le n \le 10^{18}).

출력

nn을 두 회문의 합으로 나타내는 방법의 수를 한 줄에 출력한다.

힌트

첫 번째 테스트에서 조건을 만족하는 쌍은 (5,151)(5, 151), (55,101)(55, 101), (101,55)(101, 55), (151,5)(151, 5)이다.

두 번째 테스트에서 조건을 만족하는 쌍은 (515,9009)(515, 9009), (636,8888)(636, 8888), (8888,636)(8888, 636), (9009,515)(9009, 515)이다.

세 번째 테스트에서 조건을 만족하는 쌍은 (33,42624)(33, 42624), (333,42324)(333, 42324), (4884,37773)(4884, 37773), (37773,4884)(37773, 4884), (42324,333)(42324, 333), (42624,33)(42624, 33)이다.

예제4

  1. 예제 1

    입력
    156
    
    예상 출력
    4
    
  2. 예제 2

    입력
    9524
    
    예상 출력
    4
    
  3. 예제 3

    입력
    42657
    
    예상 출력
    6
    
  4. 예제 4

    입력
    5735832847451
    
    예상 출력
    28