#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
ll ans=0;
int d[30],D[30];
int n;
void calc(){
    int i,f1,f2,f,ls;
    ll tmp=1;
    if(d[n]||n==1) return;
    for(i=1;i<=n/2;i++){
        f1=d[i-1]+D[i]-10*d[i];
        f2=d[n-i]+D[n-i+1]-10*d[n-i+1];
        if(f1+f2==0){
            ls=10-max(f1,f2);
            if(i==1&&f1<=0) ls--;
            if(ls<0) return;
            tmp*=ls;
        }
        else return;
    }
    if(n&1){
        i=n/2+1;
        f=d[i-1]+D[i]-10*d[i];
        if(f==0) tmp*=10;
        else return;
    }
    ans+=tmp;
}
void dfs(int x){
    if(x>n){calc();return;}
    d[x]=1;dfs(x+1);
    d[x]=0;dfs(x+1);
}
int main(){
    int x=0,i,mxlen,p;
    scanf("%d",&p);
    for(i=1;i<=9;i++) D[++x]=p%10,p/=10;
    for(i=x;i>=1;i--) if(D[i]) break;
    mxlen=i;
    for(n=mxlen;n<=20;n++)
        dfs(1);
    printf("%lld",ans);
    return 0;
}

### Prompt

Your challenge is to write a CPP solution 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 <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
ll ans=0;
int d[30],D[30];
int n;
void calc(){
    int i,f1,f2,f,ls;
    ll tmp=1;
    if(d[n]||n==1) return;
    for(i=1;i<=n/2;i++){
        f1=d[i-1]+D[i]-10*d[i];
        f2=d[n-i]+D[n-i+1]-10*d[n-i+1];
        if(f1+f2==0){
            ls=10-max(f1,f2);
            if(i==1&&f1<=0) ls--;
            if(ls<0) return;
            tmp*=ls;
        }
        else return;
    }
    if(n&1){
        i=n/2+1;
        f=d[i-1]+D[i]-10*d[i];
        if(f==0) tmp*=10;
        else return;
    }
    ans+=tmp;
}
void dfs(int x){
    if(x>n){calc();return;}
    d[x]=1;dfs(x+1);
    d[x]=0;dfs(x+1);
}
int main(){
    int x=0,i,mxlen,p;
    scanf("%d",&p);
    for(i=1;i<=9;i++) D[++x]=p%10,p/=10;
    for(i=x;i>=1;i--) if(D[i]) break;
    mxlen=i;
    for(n=mxlen;n<=20;n++)
        dfs(1);
    printf("%lld",ans);
    return 0;
}

```