#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int D, yyy[50], eee[50], *yks = yyy + 25, *eks = eee + 25;
ll ans;

ll Dfs (ll res, ll l, ll r) {
	if (res % l) return 0;
	if (l >= r) {
		if (res) return 0;
		else return l == r ? 10 : 1;
	} else {
		ll ret = 0, cur = r - l;
		l *= 10; r /= 10;
		for (int i = -9; i <= 9; ++i) ret += Dfs(res + cur * i, l, r) * eks[i];
		return ret;
	}
}

int main () {
	scanf("%d", &D);
	for (int i = 0; i <= 9; ++i) {
		for (int j = -9; j <= 0; ++j) {
			if (i) ++yks[i + j];
			++eks[i + j];
		}
	}
	for (ll i = 1e18; i > 1; i /= 10) {
		for (int j = -9; j <= 9; ++j) {
			ans += Dfs((i - 1) * j + D, 10, i / 10) * yks[j];
		}
	}
	printf("%lld\n", ans);
	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<bits/stdc++.h>
using namespace std;
typedef long long ll;
int D, yyy[50], eee[50], *yks = yyy + 25, *eks = eee + 25;
ll ans;

ll Dfs (ll res, ll l, ll r) {
	if (res % l) return 0;
	if (l >= r) {
		if (res) return 0;
		else return l == r ? 10 : 1;
	} else {
		ll ret = 0, cur = r - l;
		l *= 10; r /= 10;
		for (int i = -9; i <= 9; ++i) ret += Dfs(res + cur * i, l, r) * eks[i];
		return ret;
	}
}

int main () {
	scanf("%d", &D);
	for (int i = 0; i <= 9; ++i) {
		for (int j = -9; j <= 0; ++j) {
			if (i) ++yks[i + j];
			++eks[i + j];
		}
	}
	for (ll i = 1e18; i > 1; i /= 10) {
		for (int j = -9; j <= 9; ++j) {
			ans += Dfs((i - 1) * j + D, 10, i / 10) * yks[j];
		}
	}
	printf("%lld\n", ans);
	return 0;
}
```