#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll D;
const ll MAX_K = 18;
vector<ll> Pow10;
ll R;

void calc(ll hi, ll lo, ll d, ll acc) {
  if (hi <= lo) {
    if (d == 0) R += acc * (hi == lo ? 10 : 1);
    return;
  }
  ll base = Pow10[hi] - Pow10[lo];
  ll x = d / base;
  if (d < 0) ++x;
  for (ll s : {x - 2, x - 1, x, x + 1}) {
    if (s < -9 || 9 < s) continue;
    calc(hi - 1, lo + 1, d - s * base, acc * (10 - abs(s) - (lo == 0 ? 1 : 0)));
  }
}
int main() {
  cin >> D;
  Pow10.resize(MAX_K);
  Pow10[0] = 1;
  for (ll i = 1; i < MAX_K; ++i) Pow10[i] = 10 * Pow10[i - 1];
  for (ll k = 2; k <= MAX_K; ++k) {
    calc(k - 1, 0, D, 1);
  }
  cout << R << endl;
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 ll;

ll D;
const ll MAX_K = 18;
vector<ll> Pow10;
ll R;

void calc(ll hi, ll lo, ll d, ll acc) {
  if (hi <= lo) {
    if (d == 0) R += acc * (hi == lo ? 10 : 1);
    return;
  }
  ll base = Pow10[hi] - Pow10[lo];
  ll x = d / base;
  if (d < 0) ++x;
  for (ll s : {x - 2, x - 1, x, x + 1}) {
    if (s < -9 || 9 < s) continue;
    calc(hi - 1, lo + 1, d - s * base, acc * (10 - abs(s) - (lo == 0 ? 1 : 0)));
  }
}
int main() {
  cin >> D;
  Pow10.resize(MAX_K);
  Pow10[0] = 1;
  for (ll i = 1; i < MAX_K; ++i) Pow10[i] = 10 * Pow10[i - 1];
  for (ll k = 2; k <= MAX_K; ++k) {
    calc(k - 1, 0, D, 1);
  }
  cout << R << endl;
  return 0;
}

```