#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll mx[233],num[233],n,tot;

inline ll rd()
{
	ll x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline ll ksm(ll x,ll y) { ll res=1;for (;y;y>>=1,x=x*x) if (y&1) res=res*x;return res; }

inline ll dfs(ll x,ll y)
{
	if (y==tot) return (bool)(x==n);
	if (n+mx[y]<x||n-mx[y]>x) return 0;
	ll res=0;
	for (ll i=-9;i<=9;i++)
	{
		if (y) res+=dfs(x+num[y]*i,y+1)*(10-abs(i));
		else if (i!=9) res+=dfs(x+num[y]*i,y+1)*(i>=0?9LL-i:10LL+i);
	}
	return res;
}

int main()
{
	n=rd();
	ll ans=0LL;
	for (ll i=1;i<=18;i++)
	{
		memset(num,0,sizeof(num));
		memset(mx,0,sizeof(mx));
		tot=(i+1)/2;
		for (ll j=0;j<tot;j++) num[j]=ksm(10,i-j)-ksm(10,j);
		for (ll j=0;j<tot;j++) for (ll k=j;k<tot;k++) mx[j]+=num[k]*9;
		ans+=dfs(0,0)*((i%2==0)?10:1);
	}
	printf("%lld\n",ans);
	return 0;
}
### Prompt

Develop a solution in CPP 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<bits/stdc++.h>
using namespace std;
#define ll long long

ll mx[233],num[233],n,tot;

inline ll rd()
{
	ll x=0;char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar());
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

inline ll ksm(ll x,ll y) { ll res=1;for (;y;y>>=1,x=x*x) if (y&1) res=res*x;return res; }

inline ll dfs(ll x,ll y)
{
	if (y==tot) return (bool)(x==n);
	if (n+mx[y]<x||n-mx[y]>x) return 0;
	ll res=0;
	for (ll i=-9;i<=9;i++)
	{
		if (y) res+=dfs(x+num[y]*i,y+1)*(10-abs(i));
		else if (i!=9) res+=dfs(x+num[y]*i,y+1)*(i>=0?9LL-i:10LL+i);
	}
	return res;
}

int main()
{
	n=rd();
	ll ans=0LL;
	for (ll i=1;i<=18;i++)
	{
		memset(num,0,sizeof(num));
		memset(mx,0,sizeof(mx));
		tot=(i+1)/2;
		for (ll j=0;j<tot;j++) num[j]=ksm(10,i-j)-ksm(10,j);
		for (ll j=0;j<tot;j++) for (ll k=j;k<tot;k++) mx[j]+=num[k]*9;
		ans+=dfs(0,0)*((i%2==0)?10:1);
	}
	printf("%lld\n",ans);
	return 0;
}
```