#include<cstdio>

typedef long long ll;ll s,a[19];
ll dfs(int l,int e,int r,ll d,ll b)
{
	if(l--==e)return d?0:e==r?10:1;
	if(d%a[r]!=0)return 0;
	ll c=0;
	for(int i=-9;i<=(r?9:8);i++)
		c+=(i<0?10+i:r?10-i:9-i)*dfs(l,e,r+1,d-i*b,b-a[l]-a[r]);
	return c;
}

int main()
{
	int d,i=1;scanf("%d",&d);
	for(ll b=*a=9;i<20;b=b*10+9,a[i]=a[i-1]*10,i++)
		s+=dfs(i,i>>1,0,d,b);
	printf("%lld\n",s);
}
### 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<cstdio>

typedef long long ll;ll s,a[19];
ll dfs(int l,int e,int r,ll d,ll b)
{
	if(l--==e)return d?0:e==r?10:1;
	if(d%a[r]!=0)return 0;
	ll c=0;
	for(int i=-9;i<=(r?9:8);i++)
		c+=(i<0?10+i:r?10-i:9-i)*dfs(l,e,r+1,d-i*b,b-a[l]-a[r]);
	return c;
}

int main()
{
	int d,i=1;scanf("%d",&d);
	for(ll b=*a=9;i<20;b=b*10+9,a[i]=a[i-1]*10,i++)
		s+=dfs(i,i>>1,0,d,b);
	printf("%lld\n",s);
}
```