#include "bits/stdc++.h"
using namespace std;
typedef long long li;

li rec(const li dist, const li rem, const bool istop) {
    if (dist < 0) {
        return rem == 0;
    } else if (dist == 0) {
        return (rem == 0) * (10 - istop);
    }

    li unit = 1;
    for (int i = 0; i < dist; ++i) {
        unit *= 10;
    }
    unit -= 1;

    li ans = 0;
    for (int v = -9; v <= 9; ++v) {
        const li nrem = rem - unit * v;
        if (nrem % 10 == 0) {
            ans += (10 - istop - abs(v)) * rec(dist - 2, nrem / 10, false);
        }
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    li d;
    cin >> d;

    li ans = 0;
    for (int digits = 1; digits <= 25; ++digits) {
        ans += rec(digits, d, true);
    }
    cout << ans << endl;
    return 0;
}
### Prompt

Your task is to create a cpp solution 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
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

li rec(const li dist, const li rem, const bool istop) {
    if (dist < 0) {
        return rem == 0;
    } else if (dist == 0) {
        return (rem == 0) * (10 - istop);
    }

    li unit = 1;
    for (int i = 0; i < dist; ++i) {
        unit *= 10;
    }
    unit -= 1;

    li ans = 0;
    for (int v = -9; v <= 9; ++v) {
        const li nrem = rem - unit * v;
        if (nrem % 10 == 0) {
            ans += (10 - istop - abs(v)) * rec(dist - 2, nrem / 10, false);
        }
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    li d;
    cin >> d;

    li ans = 0;
    for (int digits = 1; digits <= 25; ++digits) {
        ans += rec(digits, d, true);
    }
    cout << ans << endl;
    return 0;
}
```