#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define mp make_pair

ll Pow10[19];

ll solve(ll n, int k, bool fl) {
	if (k == 0) {
		if (n == 0)
			return 1;
		else
			return 0;
	}
	if (k == 1) {
		if (n == 0)
			return 10;
		else
			return 0;
	}
	int d = n % 10;
	d = -d + 10;
	if (d == 10)
		d = 0;
	n -= d * (Pow10[k - 1] - 1);
	n /= 10;
	//cout << d << " " << n << endl;
	if (n < 0)
		n = -n;
	ll res = solve(n, k - 2, true);
	ll coef = 9 - d;
	if (fl)
		coef++;
	return res * coef;
}

int main() {
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);	
	ll n;
	cin >> n;
	ll res = 0;
	Pow10[0] = 1;
	for (int i = 1; i < 19; i++)
		Pow10[i] = Pow10[i - 1] * 10;
	for (int i = 0; i <= 18; i++)
		res += solve(n, i, false);
	cout << res << endl;
	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 <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define mp make_pair

ll Pow10[19];

ll solve(ll n, int k, bool fl) {
	if (k == 0) {
		if (n == 0)
			return 1;
		else
			return 0;
	}
	if (k == 1) {
		if (n == 0)
			return 10;
		else
			return 0;
	}
	int d = n % 10;
	d = -d + 10;
	if (d == 10)
		d = 0;
	n -= d * (Pow10[k - 1] - 1);
	n /= 10;
	//cout << d << " " << n << endl;
	if (n < 0)
		n = -n;
	ll res = solve(n, k - 2, true);
	ll coef = 9 - d;
	if (fl)
		coef++;
	return res * coef;
}

int main() {
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);	
	ll n;
	cin >> n;
	ll res = 0;
	Pow10[0] = 1;
	for (int i = 1; i < 19; i++)
		Pow10[i] = Pow10[i - 1] * 10;
	for (int i = 0; i <= 18; i++)
		res += solve(n, i, false);
	cout << res << endl;
	return 0;
}
```