#include <bits/stdc++.h>

typedef long long LL;
const int B = 12;

LL dp[B][2][2], ans;
int d[B * 2];
void solve(int b) {
	std::memset(dp, 0, sizeof dp);
	int p = b + 1 >> 1; dp[0][0][0] = 1;
	for (int i = 0; i < p; ++i) {
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k) if (LL v = dp[i][j][k]) {
				for (int x = 0; x <= 9; ++x) {
					int l = x + d[i] + j, _j = 0, _k = 0;
					if (l >= 10) _j = 1, l -= 10;
					if (!i && !l) continue;
					_k = x + k * 10 - l - d[b - i];
					if (_k == 0 || _k == 1) dp[i + 1][_j][_k] += v;
				}
			}
	}
	if (b & 1) ans += dp[p][0][0] + dp[p][1][1];
	else {
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				if (d[p] + j == k * 10) ans += dp[p][j][k] * 10;
	}
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	int _d, tot = -1; std::cin >> _d;
	while (_d) d[++tot] = _d % 10, _d /= 10;
	for (int b = tot; b <= tot * 2 + 2; ++b) solve(b);
	std::cout << ans << '\n';
	return 0;
}
### Prompt

Generate 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>

typedef long long LL;
const int B = 12;

LL dp[B][2][2], ans;
int d[B * 2];
void solve(int b) {
	std::memset(dp, 0, sizeof dp);
	int p = b + 1 >> 1; dp[0][0][0] = 1;
	for (int i = 0; i < p; ++i) {
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k) if (LL v = dp[i][j][k]) {
				for (int x = 0; x <= 9; ++x) {
					int l = x + d[i] + j, _j = 0, _k = 0;
					if (l >= 10) _j = 1, l -= 10;
					if (!i && !l) continue;
					_k = x + k * 10 - l - d[b - i];
					if (_k == 0 || _k == 1) dp[i + 1][_j][_k] += v;
				}
			}
	}
	if (b & 1) ans += dp[p][0][0] + dp[p][1][1];
	else {
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				if (d[p] + j == k * 10) ans += dp[p][j][k] * 10;
	}
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	int _d, tot = -1; std::cin >> _d;
	while (_d) d[++tot] = _d % 10, _d /= 10;
	for (int b = tot; b <= tot * 2 + 2; ++b) solve(b);
	std::cout << ans << '\n';
	return 0;
}
```