#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int num[19]={1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1};

map <ll,ll> mp;
int mx1,mx2;
ll mulv[20],powd[20];

void dfs1(int d,ll s1,ll s2) {
  if (d>mx1) {
  	mp[s1]+=s2;
  	return;
  }
  for(int i=-9;i<=9;i++) {
  	int t=num[i+9]-(d==1);
  	dfs1(d+1,s1+i*mulv[d],s2*t);
  }
}

ll sum,n;

void dfs2(int d,ll s1,ll s2) {
  if (d>mx2) {
  	if (mp.count(n-s1)) sum+=s2*mp[n-s1];
  	return;
  }
  for(int i=-9;i<=9;i++) {
  	int t=num[i+9]-(d==1);
  	dfs2(d+1,s1+i*mulv[d],s2*t);
  }
}

int main() {
  scanf("%lld",&n);
  int cnt=0;
  for(ll i=n;i;i/=10) cnt++;
  powd[0]=1;
  for(int i=1;i<=2*cnt;i++) powd[i]=powd[i-1]*10;
  ll ans=0;
  for(int i=cnt;i<=2*cnt;i++) {
  	mp.clear();
  	sum=0;
  	mx2=(i>>1);mx1=(mx2>>1);
  	for(int j=1;j<=mx2;j++) mulv[j]=powd[i-j]-powd[j-1];
  	dfs1(1,0,1);
  	dfs2(mx1+1,0,1);
  	if (i&1) sum*=10;
  	ans+=sum;
  }
  printf("%lld\n",ans);
  return 0;
}
### Prompt

Please create a solution in CPP 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 <cstring>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int num[19]={1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1};

map <ll,ll> mp;
int mx1,mx2;
ll mulv[20],powd[20];

void dfs1(int d,ll s1,ll s2) {
  if (d>mx1) {
  	mp[s1]+=s2;
  	return;
  }
  for(int i=-9;i<=9;i++) {
  	int t=num[i+9]-(d==1);
  	dfs1(d+1,s1+i*mulv[d],s2*t);
  }
}

ll sum,n;

void dfs2(int d,ll s1,ll s2) {
  if (d>mx2) {
  	if (mp.count(n-s1)) sum+=s2*mp[n-s1];
  	return;
  }
  for(int i=-9;i<=9;i++) {
  	int t=num[i+9]-(d==1);
  	dfs2(d+1,s1+i*mulv[d],s2*t);
  }
}

int main() {
  scanf("%lld",&n);
  int cnt=0;
  for(ll i=n;i;i/=10) cnt++;
  powd[0]=1;
  for(int i=1;i<=2*cnt;i++) powd[i]=powd[i-1]*10;
  ll ans=0;
  for(int i=cnt;i<=2*cnt;i++) {
  	mp.clear();
  	sum=0;
  	mx2=(i>>1);mx1=(mx2>>1);
  	for(int j=1;j<=mx2;j++) mulv[j]=powd[i-j]-powd[j-1];
  	dfs1(1,0,1);
  	dfs2(mx1+1,0,1);
  	if (i&1) sum*=10;
  	ans+=sum;
  }
  printf("%lld\n",ans);
  return 0;
}
```