#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int N, c; bool f; long long val[11], lim[11];
long long solve(long long cur, int d) {
	if (f && d + 1 == c) return 10;
	if (d == c) return 1;
	long long ret = 0;
	for (int i = -9; i <= 9; i++) {
		long long x = cur + val[d] * i;
		if (abs(N - x) <= lim[d + 1]) ret += solve(x, d + 1) * ((d == 0 ? 9 : 10) - abs(i));
	}
	return ret;
}
int main() {
	cin >> N;
	long long ret = 0;
	for (int i = 2; i <= 18; i++) {
		c = (i + 1) / 2; f = (i % 2 == 1);
		int mul = 1;
		for (int j = 0; j < c; j++) {
			string s = to_string(mul); while (s.size() < i) s = '0' + s; reverse(s.begin(), s.end());
			val[j] = stoll(s) - mul;
			mul *= 10;
		}
		for (int j = c - 1; j >= 0; j--) lim[j] = lim[j + 1] + val[j] * 9;
		ret += solve(0, 0);
	}
	cout << ret << endl;
	return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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 <string>
#include <iostream>
#include <algorithm>
using namespace std;
int N, c; bool f; long long val[11], lim[11];
long long solve(long long cur, int d) {
	if (f && d + 1 == c) return 10;
	if (d == c) return 1;
	long long ret = 0;
	for (int i = -9; i <= 9; i++) {
		long long x = cur + val[d] * i;
		if (abs(N - x) <= lim[d + 1]) ret += solve(x, d + 1) * ((d == 0 ? 9 : 10) - abs(i));
	}
	return ret;
}
int main() {
	cin >> N;
	long long ret = 0;
	for (int i = 2; i <= 18; i++) {
		c = (i + 1) / 2; f = (i % 2 == 1);
		int mul = 1;
		for (int j = 0; j < c; j++) {
			string s = to_string(mul); while (s.size() < i) s = '0' + s; reverse(s.begin(), s.end());
			val[j] = stoll(s) - mul;
			mul *= 10;
		}
		for (int j = c - 1; j >= 0; j--) lim[j] = lim[j + 1] + val[j] * 9;
		ret += solve(0, 0);
	}
	cout << ret << endl;
	return 0;
}
```