#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using db = double;
#define pb push_back

ll d;
ll ans = 0;
ll p[19];
#define dig(x, i) ((x) / p[i] % 10)

map<int,int> pm, pf;

void dfs(ll s, int n, int i, ll mul) {
	if (i * 2 + 1 == n) {
		ans += !s * mul * 10;
		return;
	}
	if (i < n / 2) {
		ans += !s * mul;
		return;
	}
	if (i < 19 && abs(s) > p[i + 1])
		return;
	for (auto j : (i == n - 1 ? pf : pm)) if (i <= 17 || j.first == 0)
		dfs(s - j.first * (p[i] - p[n - 1 - i]), n, i - 1, mul * j.second);
}

int main() {
	cin >> d;
	
	for (int i = 0; i <= 9; ++i)
		for (int j = 0; j <= 9; ++j) {
			++pm[i - j];
			if (i)
				++pf[i - j];
		}
	
	p[0] = 1;
	for (int i = 1; i < 19; ++i)
		p[i] = p[i - 1] * 10;
	
	for (int i = 2; i <= 24; ++i)
		dfs(-d, i, i - 1, 1);
	
	cout << ans << endl;
	
	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;

using ll = long long;
using vi = vector<int>;
using db = double;
#define pb push_back

ll d;
ll ans = 0;
ll p[19];
#define dig(x, i) ((x) / p[i] % 10)

map<int,int> pm, pf;

void dfs(ll s, int n, int i, ll mul) {
	if (i * 2 + 1 == n) {
		ans += !s * mul * 10;
		return;
	}
	if (i < n / 2) {
		ans += !s * mul;
		return;
	}
	if (i < 19 && abs(s) > p[i + 1])
		return;
	for (auto j : (i == n - 1 ? pf : pm)) if (i <= 17 || j.first == 0)
		dfs(s - j.first * (p[i] - p[n - 1 - i]), n, i - 1, mul * j.second);
}

int main() {
	cin >> d;
	
	for (int i = 0; i <= 9; ++i)
		for (int j = 0; j <= 9; ++j) {
			++pm[i - j];
			if (i)
				++pf[i - j];
		}
	
	p[0] = 1;
	for (int i = 1; i < 19; ++i)
		p[i] = p[i - 1] * 10;
	
	for (int i = 2; i <= 24; ++i)
		dfs(-d, i, i - 1, 1);
	
	cout << ans << endl;
	
	return 0;
}

```