#include<cstdio>
#include<iostream>
#include<algorithm> 
using namespace std;
#define ll long long
#define MN 100000
ll u[20],un,ans;
void dfs(int x,ll d,ll k)
{
	if(x>un){if(!d)ans+=k;return;}
	if(!u[x]){if(!d)ans+=k*10;return;}
	for(int i=-9;i<=9;++i)
		if(d+i*u[x]>=-u[x]&&d+i*u[x]<=u[x])
			dfs(x+1,d+i*u[x],k*(10-abs(i)-(x==1)));
}
int main()
{
	int d,i;ll a,b,c;
	scanf("%d",&d);
	for(c=10;;c*=10)
	{
		for(a=1,b=c,un=0;a<=b;a*=10,b/=10)u[++un]=b-a;
		if(u[un]>d)break;
		dfs(1,d,1);
	}
	cout<<ans;
}
### Prompt

Generate 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<iostream>
#include<algorithm> 
using namespace std;
#define ll long long
#define MN 100000
ll u[20],un,ans;
void dfs(int x,ll d,ll k)
{
	if(x>un){if(!d)ans+=k;return;}
	if(!u[x]){if(!d)ans+=k*10;return;}
	for(int i=-9;i<=9;++i)
		if(d+i*u[x]>=-u[x]&&d+i*u[x]<=u[x])
			dfs(x+1,d+i*u[x],k*(10-abs(i)-(x==1)));
}
int main()
{
	int d,i;ll a,b,c;
	scanf("%d",&d);
	for(c=10;;c*=10)
	{
		for(a=1,b=c,un=0;a<=b;a*=10,b/=10)u[++un]=b-a;
		if(u[un]>d)break;
		dfs(1,d,1);
	}
	cout<<ans;
}
```