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

const int maxn = 22;

long long d, det[maxn], ten[maxn];
int len, mid;
long long ans, temp;

void dfs(long long now, int depth, long long cnt, int flag)
{
    if (d == now && depth > mid) {
        temp += cnt;
        return;
    }
    if (depth > mid) {return;}
    long long rua = ten[depth] - ten[len + 1 - depth];
    for (int i = -9; i <= 9; i++)
    {
        if (llabs(now + rua * i - d) >= ten[len + 1 - depth]) continue;
        dfs(now + rua * i, depth + 1, cnt * (10 - flag - abs(i)), 0);
    }
}

void init ()
{
    ten[1] = 1;
    for (int i = 2; i <= 19; i++) ten[i] = ten[i - 1] * 10;
}

int main()
{
    //freopen("C:/Users/MACHENIKE/Desktop/data.in","r",stdin);
    scanf("%lld", &d);
    init();
    for (len = 1; len <= 19; len++)
    {
        temp = 0;
        mid = len / 2;
        dfs(0, 1, 1, 1);
        if (len & 1) temp *= 10;
        ans += temp;
    }
    printf("%lld", 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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 22;

long long d, det[maxn], ten[maxn];
int len, mid;
long long ans, temp;

void dfs(long long now, int depth, long long cnt, int flag)
{
    if (d == now && depth > mid) {
        temp += cnt;
        return;
    }
    if (depth > mid) {return;}
    long long rua = ten[depth] - ten[len + 1 - depth];
    for (int i = -9; i <= 9; i++)
    {
        if (llabs(now + rua * i - d) >= ten[len + 1 - depth]) continue;
        dfs(now + rua * i, depth + 1, cnt * (10 - flag - abs(i)), 0);
    }
}

void init ()
{
    ten[1] = 1;
    for (int i = 2; i <= 19; i++) ten[i] = ten[i - 1] * 10;
}

int main()
{
    //freopen("C:/Users/MACHENIKE/Desktop/data.in","r",stdin);
    scanf("%lld", &d);
    init();
    for (len = 1; len <= 19; len++)
    {
        temp = 0;
        mid = len / 2;
        dfs(0, 1, 1, 1);
        if (len & 1) temp *= 10;
        ans += temp;
    }
    printf("%lld", ans);
    return 0;
}

```