#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int D, a[20], b[20], l;
ll ans, bin[20], c[20], ans1;
inline void dfs(int i, ll D, ll now){
	if(!now)return;
	if(i==l+1){if(!D)ans1+=now; return;}
	for(int j=-9; j<=9; j++)if(c[i]*(j-1)<D&&D<c[i]*(j+1))dfs(i+1, D-c[i]*j, now*(i==1?a[j+9]:b[j+9]));
}
inline ll check(int n){
	l=0; for(int i=1; i<=n/2; i++)c[++l]=bin[n-i]-bin[i-1];
	ans1=0; dfs(1, D, 1);
	if(n&1)return ans1*10; else return ans1;
}
int main(){
	scanf("%d", &D); ans=0;
	bin[0]=1; for(int i=1; i<=18; i++)bin[i]=bin[i-1]*10;
	memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
	for(int i=0; i<=9; i++)for(int j=1; j<=9; j++)a[i-j+9]++;
	for(int i=0; i<=9; i++)for(int j=0; j<=9; j++)b[i-j+9]++;
	for(int i=2; i<=18; i++)ans+=check(i);
	printf("%lld", ans);
	return 0;
}
### Prompt

Please formulate 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<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int D, a[20], b[20], l;
ll ans, bin[20], c[20], ans1;
inline void dfs(int i, ll D, ll now){
	if(!now)return;
	if(i==l+1){if(!D)ans1+=now; return;}
	for(int j=-9; j<=9; j++)if(c[i]*(j-1)<D&&D<c[i]*(j+1))dfs(i+1, D-c[i]*j, now*(i==1?a[j+9]:b[j+9]));
}
inline ll check(int n){
	l=0; for(int i=1; i<=n/2; i++)c[++l]=bin[n-i]-bin[i-1];
	ans1=0; dfs(1, D, 1);
	if(n&1)return ans1*10; else return ans1;
}
int main(){
	scanf("%d", &D); ans=0;
	bin[0]=1; for(int i=1; i<=18; i++)bin[i]=bin[i-1]*10;
	memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
	for(int i=0; i<=9; i++)for(int j=1; j<=9; j++)a[i-j+9]++;
	for(int i=0; i<=9; i++)for(int j=0; j<=9; j++)b[i-j+9]++;
	for(int i=2; i<=18; i++)ans+=check(i);
	printf("%lld", ans);
	return 0;
}
```