#include <iostream>
using namespace std;
typedef long long ll;

ll p[19];

ll dfs(ll l, ll i, ll x){
    if(i * 2 + 1 == l){
        if(x == 0) return 10;
        return 0;
    }
    if(i * 2 == l){
        if(x == 0) return 1;
        return 0;
    }
    ll s = p[l - i - 1] - p[i];
    ll u;
    if(l - i - 1 == 0) u = p[0] * 2;
    else u = p[l - i - 1] + p[l - i - 2] * 2;
    ll res = 0;
    for(int j = -9; j <= 9; j++){
        if(abs(x + s * j) < u){
            if(i == 0) res += dfs(l, i + 1, abs(x + s * j)) * (9 - abs(j));
            else res += dfs(l, i + 1, abs(x + s * j)) * (10 - abs(j));
        }
    }
    return res;
}

int main()
{
    ll d;
    cin >> d;
    p[0] = 1;
    for(int l = 1; l <= 18; l++) p[l] = p[l - 1] * 10;
    ll ans = 0;
    for(int l = 2; l <= 18; l++){
        if(p[l] < d) continue;
        ans += dfs(l, 0, d);
    }
    cout << ans << endl;
}

### 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 <iostream>
using namespace std;
typedef long long ll;

ll p[19];

ll dfs(ll l, ll i, ll x){
    if(i * 2 + 1 == l){
        if(x == 0) return 10;
        return 0;
    }
    if(i * 2 == l){
        if(x == 0) return 1;
        return 0;
    }
    ll s = p[l - i - 1] - p[i];
    ll u;
    if(l - i - 1 == 0) u = p[0] * 2;
    else u = p[l - i - 1] + p[l - i - 2] * 2;
    ll res = 0;
    for(int j = -9; j <= 9; j++){
        if(abs(x + s * j) < u){
            if(i == 0) res += dfs(l, i + 1, abs(x + s * j)) * (9 - abs(j));
            else res += dfs(l, i + 1, abs(x + s * j)) * (10 - abs(j));
        }
    }
    return res;
}

int main()
{
    ll d;
    cin >> d;
    p[0] = 1;
    for(int l = 1; l <= 18; l++) p[l] = p[l - 1] * 10;
    ll ans = 0;
    for(int l = 2; l <= 18; l++){
        if(p[l] < d) continue;
        ans += dfs(l, 0, d);
    }
    cout << ans << endl;
}

```