#include <bits/stdc++.h>
#define N 500006
#define mo 1000000007
using namespace std;
long long T,q,n,m,t,orz,ans,cnt,p[21],a[21],bit[21];
void so(long long x,long long y,long long w)
{
	if(x>t){
		if(y!=0)return;
		if(w>0)ans+=w*(orz&1?10:1);
		return;
	}
	long long o=y%10,p=(10-o)%10;
	so(x+1,abs((y-p*a[x])/10),(x==1?w*(9-p):w*(10-p)));
}
int main()
{
	scanf("%lld",&n);m=n;p[0]=1;
	for(int i=1;i<=18;i++)p[i]=p[i-1]*10;
	for(long long i=2;i<=18;i++){
		n=m;t=i/2;orz=i;
		memset(a,0,sizeof a);
		for(long long j=1;j<i;j++)a[1]=a[1]*10+9;
		long long x=a[1];
		for(long long j=2;j<=t;j++)x/=100,a[j]=x;
		so(1,n,1);
	}
	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>
#define N 500006
#define mo 1000000007
using namespace std;
long long T,q,n,m,t,orz,ans,cnt,p[21],a[21],bit[21];
void so(long long x,long long y,long long w)
{
	if(x>t){
		if(y!=0)return;
		if(w>0)ans+=w*(orz&1?10:1);
		return;
	}
	long long o=y%10,p=(10-o)%10;
	so(x+1,abs((y-p*a[x])/10),(x==1?w*(9-p):w*(10-p)));
}
int main()
{
	scanf("%lld",&n);m=n;p[0]=1;
	for(int i=1;i<=18;i++)p[i]=p[i-1]*10;
	for(long long i=2;i<=18;i++){
		n=m;t=i/2;orz=i;
		memset(a,0,sizeof a);
		for(long long j=1;j<i;j++)a[1]=a[1]*10+9;
		long long x=a[1];
		for(long long j=2;j<=t;j++)x/=100,a[j]=x;
		so(1,n,1);
	}
	printf("%lld\n",ans);
}
```