#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int a[25],n,m,b[25];
ll ans=0;
void dfs(int k,int op,ll w){
	if(!k){
		if(!op) ans+=w;
		return;
	}
	if(k+k<=m){
		int x=(op?10:0)-b[m-k+1];
		if(x!=a[k]&&x!=a[k]+1) return;
		dfs(k-1,x==a[k]+1,w);
		return;
	}
	if((m&1)&&k+k-1==m){
		if(op&&a[k]!=9) return;
		if(!op&&a[k]!=0) return;
		dfs(k-1,op,w*10);
		return;
	}
	int l=a[k],r=a[k]+9;
	if(op) l-=10,r-=10;
	r=min(r,9);l=max(l,0);
	if(k==m&&a[k]>=l&&a[k]<=r) l++;
	if(l<=r) b[k]=(op?a[k]-10:a[k]),dfs(k-1,0,w*(r-l+1));
	l=a[k]+1;r=a[k]+10;
	if(op) l-=10,r-=10;
	l=max(l,0);r=min(r,9);
	if(k==m&&a[k]+1>=l&&a[k]+1<=r) l++;
	if(l<=r) b[k]=(op?a[k]-9:a[k]+1),dfs(k-1,1,w*(r-l+1));
	/*for(int i=0,x;i<=9;i++){
		b[k]=i;x=i+(op?10:0);
		b[m-k+1]=x-a[k];
		if(b[m-k+1]<=9&&b[m-k+1]>=0) dfs(k-1,0);
		b[m-k+1]=x-a[k]-1;
		if(b[m-k+1]<=9&&b[m-k+1]>=0) dfs(k-1,1);
	}*/
}
int main(){
	int x;
	scanf("%d",&x);
	while(x) a[++n]=x%10,x/=10;
	for(int i=n;i<=20;i++) 
		m=i,dfs(i,0,1);
	printf("%lld",ans);
	return 0;
}
### Prompt

Please create a solution in CPP 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 <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int a[25],n,m,b[25];
ll ans=0;
void dfs(int k,int op,ll w){
	if(!k){
		if(!op) ans+=w;
		return;
	}
	if(k+k<=m){
		int x=(op?10:0)-b[m-k+1];
		if(x!=a[k]&&x!=a[k]+1) return;
		dfs(k-1,x==a[k]+1,w);
		return;
	}
	if((m&1)&&k+k-1==m){
		if(op&&a[k]!=9) return;
		if(!op&&a[k]!=0) return;
		dfs(k-1,op,w*10);
		return;
	}
	int l=a[k],r=a[k]+9;
	if(op) l-=10,r-=10;
	r=min(r,9);l=max(l,0);
	if(k==m&&a[k]>=l&&a[k]<=r) l++;
	if(l<=r) b[k]=(op?a[k]-10:a[k]),dfs(k-1,0,w*(r-l+1));
	l=a[k]+1;r=a[k]+10;
	if(op) l-=10,r-=10;
	l=max(l,0);r=min(r,9);
	if(k==m&&a[k]+1>=l&&a[k]+1<=r) l++;
	if(l<=r) b[k]=(op?a[k]-9:a[k]+1),dfs(k-1,1,w*(r-l+1));
	/*for(int i=0,x;i<=9;i++){
		b[k]=i;x=i+(op?10:0);
		b[m-k+1]=x-a[k];
		if(b[m-k+1]<=9&&b[m-k+1]>=0) dfs(k-1,0);
		b[m-k+1]=x-a[k]-1;
		if(b[m-k+1]<=9&&b[m-k+1]>=0) dfs(k-1,1);
	}*/
}
int main(){
	int x;
	scanf("%d",&x);
	while(x) a[++n]=x%10,x/=10;
	for(int i=n;i<=20;i++) 
		m=i,dfs(i,0,1);
	printf("%lld",ans);
	return 0;
}
```