#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int lim=18;
ll ans,pw[31],a[31],b[31],k,tmp;
int i,j,n;
ll av(ll x){
	return (x>=0)?x:-x;
}
ll work(int n){
	ll res=1;
	int i;
	if (n&1) res=10;
	for (i=1;i<=n/2;i++){
		if (b[i]==0){
			res*=((i==1)?9:10);continue;
		}
		if (b[i]<0){
			res*=(10+b[i]);
		}else{
			if (i==1){
				if (b[i]==9) return 0;
				res*=9-b[i];
			}else{
				res*=10-b[i];
			}
		}
	}
	return res;
}
void dfs(int x,int n,ll p,ll v){
	int i;
	if (x>1&&av(p-v)>a[x-1]) return;
	if (x>n/2){
		if (p!=v) return;
		tmp+=work(n);
		return;
	}
	for (i=-9;i<=9;i++){
		b[x]=i;
		dfs(x+1,n,p,v+a[x]*(ll)i);
	}
}
ll calc(int x,int n){
	int i;
	for (i=1;i<=n/2;i++) a[i]=pw[n-i]-pw[i-1];
	tmp=0;dfs(1,n,x,0);
	return tmp;
}
int main(){
	for (i=pw[0]=1;i<=lim;i++) pw[i]=10LL*pw[i-1];
	scanf("%d",&n);
	for (i=2,ans=0;i<=lim;i++) ans+=calc(n,i);//,printf("%d %lld\n",i,ans);
	printf("%lld\n",ans);
	return 0;
}
### 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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int lim=18;
ll ans,pw[31],a[31],b[31],k,tmp;
int i,j,n;
ll av(ll x){
	return (x>=0)?x:-x;
}
ll work(int n){
	ll res=1;
	int i;
	if (n&1) res=10;
	for (i=1;i<=n/2;i++){
		if (b[i]==0){
			res*=((i==1)?9:10);continue;
		}
		if (b[i]<0){
			res*=(10+b[i]);
		}else{
			if (i==1){
				if (b[i]==9) return 0;
				res*=9-b[i];
			}else{
				res*=10-b[i];
			}
		}
	}
	return res;
}
void dfs(int x,int n,ll p,ll v){
	int i;
	if (x>1&&av(p-v)>a[x-1]) return;
	if (x>n/2){
		if (p!=v) return;
		tmp+=work(n);
		return;
	}
	for (i=-9;i<=9;i++){
		b[x]=i;
		dfs(x+1,n,p,v+a[x]*(ll)i);
	}
}
ll calc(int x,int n){
	int i;
	for (i=1;i<=n/2;i++) a[i]=pw[n-i]-pw[i-1];
	tmp=0;dfs(1,n,x,0);
	return tmp;
}
int main(){
	for (i=pw[0]=1;i<=lim;i++) pw[i]=10LL*pw[i-1];
	scanf("%d",&n);
	for (i=2,ans=0;i<=lim;i++) ans+=calc(n,i);//,printf("%d %lld\n",i,ans);
	printf("%lld\n",ans);
	return 0;
}
```