#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long i64;

int D, n;
i64 p10[20], w[20];

//1000000000

i64 dfs(int i, i64 D) {
	//printf("%d %lld %lld\n", i, D, w[i]);
	if (abs(D) > 10 * w[i]) return 0;
	if (i * 2 > n) {
	//	printf("%lld %lld\n", w[i], D);
		
		if (D != 0) return 0;
		else if (i * 2 == n + 1) return 10;
		else return 1;
	}
	i64 ans = 0;
	for (int d = -9; d <= 9; ++d) {
		int l = i == 1 ? 1 : 0, r = 9;
		l = max(l, -d), r = min(r, 9 - d);
		if (l > r) continue;
		//if (n == 2 && i == 1 && d == 7) printf("%d %d\n", l, r);
		ans += (r - l + 1) * dfs(i + 1, D - d * w[i]);
	}
	return ans;
}

int main() {
	scanf("%d", &D);
	i64 ans = 0;
	p10[0] = 1;
	for (int i = 1; i <= 18; ++i)
		p10[i] = p10[i - 1] * 10;
	for (int i = 2; i <= 18; ++i) {
		n = i;
		for (int k = 1; k <= n / 2; ++k) w[k] = p10[n - k] - p10[k - 1];//, printf("%lld ", w[k]);
		//puts("");
		ans += dfs(1, D);
	}
	printf("%lld\n", ans);
	return 0;
}
### Prompt

Create a solution in CPP for 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 <algorithm>
using namespace std;

typedef long long i64;

int D, n;
i64 p10[20], w[20];

//1000000000

i64 dfs(int i, i64 D) {
	//printf("%d %lld %lld\n", i, D, w[i]);
	if (abs(D) > 10 * w[i]) return 0;
	if (i * 2 > n) {
	//	printf("%lld %lld\n", w[i], D);
		
		if (D != 0) return 0;
		else if (i * 2 == n + 1) return 10;
		else return 1;
	}
	i64 ans = 0;
	for (int d = -9; d <= 9; ++d) {
		int l = i == 1 ? 1 : 0, r = 9;
		l = max(l, -d), r = min(r, 9 - d);
		if (l > r) continue;
		//if (n == 2 && i == 1 && d == 7) printf("%d %d\n", l, r);
		ans += (r - l + 1) * dfs(i + 1, D - d * w[i]);
	}
	return ans;
}

int main() {
	scanf("%d", &D);
	i64 ans = 0;
	p10[0] = 1;
	for (int i = 1; i <= 18; ++i)
		p10[i] = p10[i - 1] * 10;
	for (int i = 2; i <= 18; ++i) {
		n = i;
		for (int k = 1; k <= n / 2; ++k) w[k] = p10[n - k] - p10[k - 1];//, printf("%lld ", w[k]);
		//puts("");
		ans += dfs(1, D);
	}
	printf("%lld\n", ans);
	return 0;
}
```