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

#define mp(x, y) make_pair((x), (y))

typedef long long ll;

ll ten[42];

ll d;

ll ans(ll D, int a, int b, int z=0) {
	ll DD=D;
	int aa=a, bb=b;
	while(aa>bb) {
		DD+=9*(ten[aa]-ten[bb]);
		aa--;
		bb++;
	}
	if(DD<0) return 0;
	DD=D;
	aa=a; bb=b;
	while(aa>bb) {
		DD-=9*(ten[aa]-ten[bb]);
		aa--;
		bb++;
	}
	if(DD>0) return 0;
	if(a<b) {
		if(D==0) return 1;
		else return 0;
	} else if(a==b) {
		if(D==0) return 9+z;
		else return 0;
	}
	ll ret=0;
	for(int d=-(8+z); d<=8+z; d++) {
		ret+=(9+z-abs(d))*ans(D-d*(ten[a]-ten[b]), a-1, b+1, 1);
	}
	return ret;
}

int main()
{
	ten[0]=1;
	for(int i=1; i<=18; i++) ten[i]=10*ten[i-1];
	scanf("%lld", &d);
	ll a=0;
	for(int i=0; i<=18; i++) {
		a+=ans(d, i, 0);
	}
	printf("%lld\n", a);

	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 <bits/stdc++.h>
using namespace std;

#define mp(x, y) make_pair((x), (y))

typedef long long ll;

ll ten[42];

ll d;

ll ans(ll D, int a, int b, int z=0) {
	ll DD=D;
	int aa=a, bb=b;
	while(aa>bb) {
		DD+=9*(ten[aa]-ten[bb]);
		aa--;
		bb++;
	}
	if(DD<0) return 0;
	DD=D;
	aa=a; bb=b;
	while(aa>bb) {
		DD-=9*(ten[aa]-ten[bb]);
		aa--;
		bb++;
	}
	if(DD>0) return 0;
	if(a<b) {
		if(D==0) return 1;
		else return 0;
	} else if(a==b) {
		if(D==0) return 9+z;
		else return 0;
	}
	ll ret=0;
	for(int d=-(8+z); d<=8+z; d++) {
		ret+=(9+z-abs(d))*ans(D-d*(ten[a]-ten[b]), a-1, b+1, 1);
	}
	return ret;
}

int main()
{
	ten[0]=1;
	for(int i=1; i<=18; i++) ten[i]=10*ten[i-1];
	scanf("%lld", &d);
	ll a=0;
	for(int i=0; i<=18; i++) {
		a+=ans(d, i, 0);
	}
	printf("%lld\n", a);

	return 0;
}
```