#include<cstdio> 
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
const int N=2e6+5,M=1e7+50,mo=1e9+7;
ll ten[20],inc[20],ans,d,upb,i,j,cons,L,D[N],xs;
void dfs(int x,ll y,ll z)
{
	if (x>L/2-1)
	{
		if (L%2) z*=10;
		if (y==d)
			ans+=z;
		return ;
	}
	ll i=-9;
	while (i<=9&&y+i*(ten[L-x-1]-ten[x])<=d) i++;
	i--;
	D[x]=i;
	dfs(x+1,y+i*(ten[L-x-1]-ten[x]),z*(inc[i+cons]-(x==0&&i>=0)));
	i++;
	if (i>9) return ;
	D[x]=i;
	dfs(x+1,y+i*(ten[L-x-1]-ten[x]),z*(inc[i+cons]-(x==0&&i>=0)));
	//d[i]=s[i]-s[l-1-i]，gx=d[i]*(10^i-10^(l-i-1)) , 
	//s[L-1]!=0, 当d>=0,存在s[L-1]=0 
}
int main()
{
	scanf("%lld",&d);
	xs=1;
	//while (d%10==0) d/=10,xs*=10;
	ten[0]=1;
	fo(i,1,18) ten[i]=ten[i-1]*10;
	cons=10;
	fo(i,0,9) fo(j,0,9) inc[i-j+cons]++;
	fo(upb,0,9) if (ten[upb]>d) break;
	fo(L,0,19)
		dfs(0,0,1);
	//xs=xs/10*9; 
	printf("%lld",ans*xs);
}
### Prompt

In Cpp, your task is to solve 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<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
const int N=2e6+5,M=1e7+50,mo=1e9+7;
ll ten[20],inc[20],ans,d,upb,i,j,cons,L,D[N],xs;
void dfs(int x,ll y,ll z)
{
	if (x>L/2-1)
	{
		if (L%2) z*=10;
		if (y==d)
			ans+=z;
		return ;
	}
	ll i=-9;
	while (i<=9&&y+i*(ten[L-x-1]-ten[x])<=d) i++;
	i--;
	D[x]=i;
	dfs(x+1,y+i*(ten[L-x-1]-ten[x]),z*(inc[i+cons]-(x==0&&i>=0)));
	i++;
	if (i>9) return ;
	D[x]=i;
	dfs(x+1,y+i*(ten[L-x-1]-ten[x]),z*(inc[i+cons]-(x==0&&i>=0)));
	//d[i]=s[i]-s[l-1-i]，gx=d[i]*(10^i-10^(l-i-1)) , 
	//s[L-1]!=0, 当d>=0,存在s[L-1]=0 
}
int main()
{
	scanf("%lld",&d);
	xs=1;
	//while (d%10==0) d/=10,xs*=10;
	ten[0]=1;
	fo(i,1,18) ten[i]=ten[i-1]*10;
	cons=10;
	fo(i,0,9) fo(j,0,9) inc[i-j+cons]++;
	fo(upb,0,9) if (ten[upb]>d) break;
	fo(L,0,19)
		dfs(0,0,1);
	//xs=xs/10*9; 
	printf("%lld",ans*xs);
}
```