#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 20
#define ll long long
using namespace std;
int d,n=0;
ll e[N],a[N],b[N],m,ans=0;
void dg(ll x,ll y,ll z)
{
	if(x>=m/2)
	{
		if(m%2==1) z*=10;
		if(y==d) ans+=z;
		return;
	}
	ll q=-9;
	while(q<=9&&y+q*(e[m-x-1]-e[x])<=d) q++;
	q--;
	dg(x+1,y+q*(e[m-x-1]-e[x]),z*b[q+10]-(x==0&&q>=0));
	q++;
	if(q>9) return;
	dg(x+1,y+q*(e[m-x-1]-e[x]),z*b[q+10]-(x==0&&q>=0));
}
int main()
{
	e[0]=1;fo(i,1,18) e[i]=e[i-1]*10;
	scanf("%d",&d);
	n=0;
	for(int a=d;a;a/=10) n++;
	fo(i,0,9) fo(j,0,9) b[i-j+10]++;
	for(m=1;m<=18;m++) dg(0,0,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<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 20
#define ll long long
using namespace std;
int d,n=0;
ll e[N],a[N],b[N],m,ans=0;
void dg(ll x,ll y,ll z)
{
	if(x>=m/2)
	{
		if(m%2==1) z*=10;
		if(y==d) ans+=z;
		return;
	}
	ll q=-9;
	while(q<=9&&y+q*(e[m-x-1]-e[x])<=d) q++;
	q--;
	dg(x+1,y+q*(e[m-x-1]-e[x]),z*b[q+10]-(x==0&&q>=0));
	q++;
	if(q>9) return;
	dg(x+1,y+q*(e[m-x-1]-e[x]),z*b[q+10]-(x==0&&q>=0));
}
int main()
{
	e[0]=1;fo(i,1,18) e[i]=e[i-1]*10;
	scanf("%d",&d);
	n=0;
	for(int a=d;a;a/=10) n++;
	fo(i,0,9) fo(j,0,9) b[i-j+10]++;
	for(m=1;m<=18;m++) dg(0,0,1);
	printf("%lld\n",ans);
}
```