#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
long long p[maxn], w[maxn * maxn];
unordered_map<int, int> W, W2;
int stk = 0;
long long dfs(int p, long long d){
	long long mx = 0;
	for(int i = p; i < stk; i++) mx += w[i] * 9;
	if(d < -mx || mx < d) return 0;
	if(p == stk){
		return d == 0;
	}
	long long ans = 0;
	for(int i = -9; i <= 9; i++) ans += (p == 0 ? W2 : W)[i] * dfs(p + 1, d - i * w[p]);
	return ans;
}
long long calc(int len, long long d){
	stk = 0;
	int i = 0, j = len - 1;
	while(j > i){
		w[stk++] = p[j] - p[i];
		j--;
		i++;
	}
	return dfs(0, d) * ((len&1)?10:1);
}
int main(){
	for(int i = 0; i <= 9; i++) for(int j = 0; j <= 9; j++) W[i - j]++;
	for(int i = 0; i <= 9; i++) for(int j = 1; j <= 9; j++) W2[i - j]++;
	p[0] = 1;
	for(int i = 1; i < maxn; i++) p[i] = 10ll * p[i - 1];
	int d; cin >> d;
	long long ans = 0;
	for(int i = 2; i <= 18; i++) ans += calc(i, d);
	cout << ans << endl;
	return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
const int maxn = 20;
long long p[maxn], w[maxn * maxn];
unordered_map<int, int> W, W2;
int stk = 0;
long long dfs(int p, long long d){
	long long mx = 0;
	for(int i = p; i < stk; i++) mx += w[i] * 9;
	if(d < -mx || mx < d) return 0;
	if(p == stk){
		return d == 0;
	}
	long long ans = 0;
	for(int i = -9; i <= 9; i++) ans += (p == 0 ? W2 : W)[i] * dfs(p + 1, d - i * w[p]);
	return ans;
}
long long calc(int len, long long d){
	stk = 0;
	int i = 0, j = len - 1;
	while(j > i){
		w[stk++] = p[j] - p[i];
		j--;
		i++;
	}
	return dfs(0, d) * ((len&1)?10:1);
}
int main(){
	for(int i = 0; i <= 9; i++) for(int j = 0; j <= 9; j++) W[i - j]++;
	for(int i = 0; i <= 9; i++) for(int j = 1; j <= 9; j++) W2[i - j]++;
	p[0] = 1;
	for(int i = 1; i < maxn; i++) p[i] = 10ll * p[i - 1];
	int d; cin >> d;
	long long ans = 0;
	for(int i = 2; i <= 18; i++) ans += calc(i, d);
	cout << ans << endl;
	return 0;
}

```