#include<cstdio>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=beg[j];i;i=nex[i])
using namespace std;
int const mn=15e5+3;
int n,d,cnt[25];
LL pw10[25],ans;
void dfs(int x,LL y,LL z){
	if(x>n/2-1){
		if(n&1)z*=10;
		if(y==d)
			ans+=z;
		return;
	}
	int i=-9;
	for(;(i+1<=9)&&(y+(i+1)*(pw10[n-x-1]-pw10[x]))<d;i++);
	dfs(x+1,y+i*(pw10[n-x-1]-pw10[x]),z*(cnt[i+10]-((!x)&&(i>=0))));
	if(i+1<=9)i++,dfs(x+1,y+i*(pw10[n-x-1]-pw10[x]),z*(cnt[i+10]-((!x)&&(i>=0))));
}
int main(){
	scanf("%d",&d);
	pw10[0]=1;
	fo(i,1,19)pw10[i]=pw10[i-1]*10;
	fo(i,0,9)fo(j,0,9)cnt[i-j+10]++;
	fo(i,2,19)n=i,dfs(0,0,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<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=beg[j];i;i=nex[i])
using namespace std;
int const mn=15e5+3;
int n,d,cnt[25];
LL pw10[25],ans;
void dfs(int x,LL y,LL z){
	if(x>n/2-1){
		if(n&1)z*=10;
		if(y==d)
			ans+=z;
		return;
	}
	int i=-9;
	for(;(i+1<=9)&&(y+(i+1)*(pw10[n-x-1]-pw10[x]))<d;i++);
	dfs(x+1,y+i*(pw10[n-x-1]-pw10[x]),z*(cnt[i+10]-((!x)&&(i>=0))));
	if(i+1<=9)i++,dfs(x+1,y+i*(pw10[n-x-1]-pw10[x]),z*(cnt[i+10]-((!x)&&(i>=0))));
}
int main(){
	scanf("%d",&d);
	pw10[0]=1;
	fo(i,1,19)pw10[i]=pw10[i-1]*10;
	fo(i,0,9)fo(j,0,9)cnt[i-j+10]++;
	fo(i,2,19)n=i,dfs(0,0,1);
	printf("%lld",ans);
	return 0;
}

```