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

vector<ll> po(19,1);

ll calc(int i,int j,ll e){
    if (j>i-1-j) return (e==0?1:0);
    ll res=0;
    int diff=(j==i-1-j?0:e/(po[i-1-j]-po[j]));
    for (ll d=diff-1;d<=diff+1;++d){
        if (j==i-1-j&&d!=0) continue;
        ll ne=e-(po[i-1-j]-po[j])*d;
        if (ne<-(po[i-1-j]-po[j])||po[i-1-j]-po[j]<ne) continue;
        for (int k=(!j?1:0),cnt=0;k<10;++k){
            if (k+d>=0&&k+d<10) ++cnt;
            if (k==9) res+=calc(i,j+1,ne)*cnt;
        }
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i=0;i<18;++i) po[i+1]=po[i]*10;
    int D; cin >> D;
    ll ans=0;
    for (int i=2;i<=19;++i){
        ans+=calc(i,0,D);
    }
    cout << ans << '\n';
}
### 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;

vector<ll> po(19,1);

ll calc(int i,int j,ll e){
    if (j>i-1-j) return (e==0?1:0);
    ll res=0;
    int diff=(j==i-1-j?0:e/(po[i-1-j]-po[j]));
    for (ll d=diff-1;d<=diff+1;++d){
        if (j==i-1-j&&d!=0) continue;
        ll ne=e-(po[i-1-j]-po[j])*d;
        if (ne<-(po[i-1-j]-po[j])||po[i-1-j]-po[j]<ne) continue;
        for (int k=(!j?1:0),cnt=0;k<10;++k){
            if (k+d>=0&&k+d<10) ++cnt;
            if (k==9) res+=calc(i,j+1,ne)*cnt;
        }
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int i=0;i<18;++i) po[i+1]=po[i]*10;
    int D; cin >> D;
    ll ans=0;
    for (int i=2;i<=19;++i){
        ans+=calc(i,0,D);
    }
    cout << ans << '\n';
}
```