#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll ans;
ll p10[19];

void gogo (int dhi, int dlo, ll K, ll nmult)
{
    if (dhi <= dlo)
    {
        if (dhi == dlo) nmult *= 10;
        if (!K)
            ans += nmult;
        return;
    }

    ll ndiff = p10[dhi] - p10[dlo];
    for (int i = -9; i <= 9; i++)
    {
        ll knew = K + i * ndiff;
        if (abs(knew) < p10[dhi])
        {
            int nways = 10 - abs (i);
            if (dlo == 0 && i <= 0) nways--;
            gogo (dhi - 1, dlo + 1, knew, nmult * nways);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    ans = 0;
    p10[0] = 1;
    for (int i = 1; i < 19; i++)
        p10[i] = p10[i-1] * 10;

    ll D;
    cin >> D;
    for (int ndig = 1; ndig <= 18; ndig++)
        gogo (ndig - 1, 0, D, 1);

    cout << ans << "\n";
}

### Prompt

In Cpp, your task is to solve 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 ll;

ll ans;
ll p10[19];

void gogo (int dhi, int dlo, ll K, ll nmult)
{
    if (dhi <= dlo)
    {
        if (dhi == dlo) nmult *= 10;
        if (!K)
            ans += nmult;
        return;
    }

    ll ndiff = p10[dhi] - p10[dlo];
    for (int i = -9; i <= 9; i++)
    {
        ll knew = K + i * ndiff;
        if (abs(knew) < p10[dhi])
        {
            int nways = 10 - abs (i);
            if (dlo == 0 && i <= 0) nways--;
            gogo (dhi - 1, dlo + 1, knew, nmult * nways);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    ans = 0;
    p10[0] = 1;
    for (int i = 1; i < 19; i++)
        p10[i] = p10[i-1] * 10;

    ll D;
    cin >> D;
    for (int ndig = 1; ndig <= 18; ndig++)
        gogo (ndig - 1, 0, D, 1);

    cout << ans << "\n";
}

```