#include <bits/stdc++.h>
#define yabs(x) ((x<0)?(-(x)):(x)) 

typedef long long LL;
using namespace std;

int D;
LL ppow[20];

void Init() {
	scanf("%d",&D);
	ppow[0]=1ll;
	for (int i=1;i<=18;++i) ppow[i]=ppow[i-1]*10ll;
}

int Dfs(int now,int len,LL D) {
	if (yabs(D)>=ppow[len-now]) return 0;
	if (len-now-1<now) return D==0;
	if (len-now-1==now) return (D==0)*10;
	int ret=0,mx,mn;
	for (int i=-9;i<=9;++i) {
		if (!now) mx=min(9,9-i),mn=max(1,-i);	
		else mx=min(9,9-i),mn=max(0,-i);
		if (mx>=mn)
			ret+=(mx-mn+1)*Dfs(now+1,len,D-i*(ppow[len-now-1]-ppow[now]));
	}
	return ret;
}

void Solve() {
	LL ans=0;
	for (int i=0;i<=18;++i) ans+=Dfs(0,i,D);
	printf("%lld\n",ans);
}

int main() {
	Init();
	Solve();
	return 0;
}
### Prompt

Your task is to create 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 yabs(x) ((x<0)?(-(x)):(x)) 

typedef long long LL;
using namespace std;

int D;
LL ppow[20];

void Init() {
	scanf("%d",&D);
	ppow[0]=1ll;
	for (int i=1;i<=18;++i) ppow[i]=ppow[i-1]*10ll;
}

int Dfs(int now,int len,LL D) {
	if (yabs(D)>=ppow[len-now]) return 0;
	if (len-now-1<now) return D==0;
	if (len-now-1==now) return (D==0)*10;
	int ret=0,mx,mn;
	for (int i=-9;i<=9;++i) {
		if (!now) mx=min(9,9-i),mn=max(1,-i);	
		else mx=min(9,9-i),mn=max(0,-i);
		if (mx>=mn)
			ret+=(mx-mn+1)*Dfs(now+1,len,D-i*(ppow[len-now-1]-ppow[now]));
	}
	return ret;
}

void Solve() {
	LL ans=0;
	for (int i=0;i<=18;++i) ans+=Dfs(0,i,D);
	printf("%lld\n",ans);
}

int main() {
	Init();
	Solve();
	return 0;
}
```