#include <bits/stdc++.h>

using namespace std;

long long pw10[18], res = 0;
int n;

long long bt (int pos, long long rem, bool zero) {
    if (pos == 0) return (rem == 0 ? 1 : 0);
    if (pos == 1) return (rem == 0 ? 10 : 0);

    long long ans = 0;
    for (int i = -9; i <= 9; i++) {
        long long cur = rem - 1LL * i * (pw10[pos - 1] - 1);
        if (cur % 10 == 0) {
            if (!zero) {
                if (i >= 0) ans += bt(pos - 2, cur / 10, true) * (9 - abs(i));
            }
            else ans += bt(pos - 2, cur / 10, true) * (10 - abs(i));
        }
    }

    return ans;
}

int main(){
    scanf("%d", &n);

    pw10[0] = 1;
    for (int i = 1; i < 18; i++) pw10[i] = 1LL * pw10[i - 1] * 10;
    for (int i = 1; i <= 18; i++) res += bt(i, n, false);

    printf("%lld", res);
    return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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
#include <bits/stdc++.h>

using namespace std;

long long pw10[18], res = 0;
int n;

long long bt (int pos, long long rem, bool zero) {
    if (pos == 0) return (rem == 0 ? 1 : 0);
    if (pos == 1) return (rem == 0 ? 10 : 0);

    long long ans = 0;
    for (int i = -9; i <= 9; i++) {
        long long cur = rem - 1LL * i * (pw10[pos - 1] - 1);
        if (cur % 10 == 0) {
            if (!zero) {
                if (i >= 0) ans += bt(pos - 2, cur / 10, true) * (9 - abs(i));
            }
            else ans += bt(pos - 2, cur / 10, true) * (10 - abs(i));
        }
    }

    return ans;
}

int main(){
    scanf("%d", &n);

    pw10[0] = 1;
    for (int i = 1; i < 18; i++) pw10[i] = 1LL * pw10[i - 1] * 10;
    for (int i = 1; i <= 18; i++) res += bt(i, n, false);

    printf("%lld", res);
    return 0;
}

```