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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll MAX=1<<18;
const ll INF=0x3f3f3f3f;
vector<ll> w,q;
ll d,ans;
ll power(ll x,ll y){
    if(y==0) return 1;
    ll t=power(x,y/2);
    if(y%2) return t*t*x;
    return t*t;
}
ll fnum(ll val,ll idx){
    ll t=0;
    if(val>q[idx]+d||val<-q[idx]+d) return 0;
    if(idx==w.size()){
        if(val==d) return 1;
        return 0;
    }
    for(ll i=-9;i<=9;i++) {
        if(idx!=0) t+=(10-abs(i))*fnum(val+i*w[idx],idx+1);
        else t+=min(i+10,9-i)*fnum(val+i*w[idx],idx+1);
    }
    return t;
}
int main(){
    scanf("%lld",&d);
    for(ll i=1;i<20;i++){
        w.clear(); q.clear();
        for(ll j=0;j<(i+1)/2;j++){
            w.push_back(power(10,i-j)-power(10,j));
            q.push_back(0);
        }
        for(ll j=0;j<w.size();j++) {
            for(ll k=j;k<w.size();k++) q[j]+=w[k]*9;
        }
        //printf("\n");
        if(i%2==0) ans+=10*fnum(0,0);
        else ans+=fnum(0,0);
    }
    printf("%lld\n",ans);
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll MAX=1<<18;
const ll INF=0x3f3f3f3f;
vector<ll> w,q;
ll d,ans;
ll power(ll x,ll y){
    if(y==0) return 1;
    ll t=power(x,y/2);
    if(y%2) return t*t*x;
    return t*t;
}
ll fnum(ll val,ll idx){
    ll t=0;
    if(val>q[idx]+d||val<-q[idx]+d) return 0;
    if(idx==w.size()){
        if(val==d) return 1;
        return 0;
    }
    for(ll i=-9;i<=9;i++) {
        if(idx!=0) t+=(10-abs(i))*fnum(val+i*w[idx],idx+1);
        else t+=min(i+10,9-i)*fnum(val+i*w[idx],idx+1);
    }
    return t;
}
int main(){
    scanf("%lld",&d);
    for(ll i=1;i<20;i++){
        w.clear(); q.clear();
        for(ll j=0;j<(i+1)/2;j++){
            w.push_back(power(10,i-j)-power(10,j));
            q.push_back(0);
        }
        for(ll j=0;j<w.size();j++) {
            for(ll k=j;k<w.size();k++) q[j]+=w[k]*9;
        }
        //printf("\n");
        if(i%2==0) ans+=10*fnum(0,0);
        else ans+=fnum(0,0);
    }
    printf("%lld\n",ans);
}

```