#include<bits/stdc++.h>
#define LL long long
using namespace std;
int D; LL ans,ten[19],a[19];
void dfs(int t,int up,LL s,LL D)
{
	int i;
	if(abs(D)>a[t]) return ;
	if(t>(up-1)/2){ ans+=s*(~up&1 ? 10 : 1); return ;}
	for(i=-9;i<=9;i++)
		dfs(t+1,up,s*(10-abs(i)-(t==0&&i>=0)),D-i*(ten[up-t]-ten[t]));
}
int main()
{
	int i,j;
	scanf("%d",&D),ten[0]=1;
	for(i=1;i<=18;i++)
		ten[i]=ten[i-1]*10;
	for(i=1;i<=18;i++){
		memset(a,0,sizeof(a));
		for(j=0;j<=(i-1)/2;j++)
			a[j]=9*(ten[i-j]-ten[j]);
		for(j=(i-1)/2;j>=0;j--)
			a[j]+=a[j+1];
		dfs(0,i,1,D);
	  }
	cout<<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<bits/stdc++.h>
#define LL long long
using namespace std;
int D; LL ans,ten[19],a[19];
void dfs(int t,int up,LL s,LL D)
{
	int i;
	if(abs(D)>a[t]) return ;
	if(t>(up-1)/2){ ans+=s*(~up&1 ? 10 : 1); return ;}
	for(i=-9;i<=9;i++)
		dfs(t+1,up,s*(10-abs(i)-(t==0&&i>=0)),D-i*(ten[up-t]-ten[t]));
}
int main()
{
	int i,j;
	scanf("%d",&D),ten[0]=1;
	for(i=1;i<=18;i++)
		ten[i]=ten[i-1]*10;
	for(i=1;i<=18;i++){
		memset(a,0,sizeof(a));
		for(j=0;j<=(i-1)/2;j++)
			a[j]=9*(ten[i-j]-ten[j]);
		for(j=(i-1)/2;j>=0;j--)
			a[j]+=a[j+1];
		dfs(0,i,1,D);
	  }
	cout<<ans;
	return 0;
}

```