// Copyright 2017 wu_qing
#include <stdint.h>
#include <cstdio>
#include <cmath>
int64_t powe[20], d, ans;
int64_t dfs(int64_t l, int64_t r, int64_t d) {
    if (l >= r) {
        if (d == 0)
            return l == r ? 10 : 1;
        return 0;
    }
    if (d % 10 == 0) {
        if (l != 1) return 10 * dfs(l + 1, r - 1, d / 10);
        return 9 * dfs(l + 1, r - 1, d / 10);
    }
    int64_t dif = d % 10 - 10;
    int64_t nxt = d - dif + dif * powe[r - l];
    if (l == 1) return (9 + dif) * dfs(l + 1, r - 1, std::abs(nxt) / 10);
    return (10 + dif) * dfs(l + 1, r - 1, std::abs(nxt) / 10);
}
int main() {
    scanf("%lld", &d);
    powe[0] = 1;
    for (int i = 1; i <= 18; i++)
        powe[i] = powe[i - 1] * 10;
    for (int i = 2; i <= 18; i++)
        ans += dfs(1, i, d);
    printf("%lld\n", ans);
    return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

For a positive integer n, we denote the integer obtained by reversing the decimal notation of n (without leading zeroes) by rev(n). For example, rev(123) = 321 and rev(4000) = 4.

You are given a positive integer D. How many positive integers N satisfy rev(N) = N + D?

Constraints

* D is an integer.
* 1 ≤ D < 10^9

Input

Input is given from Standard Input in the following format:


D


Output

Print the number of the positive integers N such that rev(N) = N + D.

Examples

Input

63


Output

2


Input

75


Output

0


Input

864197532


Output

1920

### Response

```cpp
// Copyright 2017 wu_qing
#include <stdint.h>
#include <cstdio>
#include <cmath>
int64_t powe[20], d, ans;
int64_t dfs(int64_t l, int64_t r, int64_t d) {
    if (l >= r) {
        if (d == 0)
            return l == r ? 10 : 1;
        return 0;
    }
    if (d % 10 == 0) {
        if (l != 1) return 10 * dfs(l + 1, r - 1, d / 10);
        return 9 * dfs(l + 1, r - 1, d / 10);
    }
    int64_t dif = d % 10 - 10;
    int64_t nxt = d - dif + dif * powe[r - l];
    if (l == 1) return (9 + dif) * dfs(l + 1, r - 1, std::abs(nxt) / 10);
    return (10 + dif) * dfs(l + 1, r - 1, std::abs(nxt) / 10);
}
int main() {
    scanf("%lld", &d);
    powe[0] = 1;
    for (int i = 1; i <= 18; i++)
        powe[i] = powe[i - 1] * 10;
    for (int i = 2; i <= 18; i++)
        ans += dfs(1, i, d);
    printf("%lld\n", ans);
    return 0;
}

```