#include <bits/stdc++.h>

#define ll long long
#define MAXN (19)

ll d;
ll mi10[MAXN], wjj[MAXN], tz[MAXN];
ll orz[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
ll otz[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
ll ans;

void dfs(int j, ll now, ll tmp, bool mmm = false){
	if(j == 0){
		if(now == d) ans += tmp;
		return;
	}
	
	if(now + 9 * tz[j] < d) return;
	if(now - 9 * tz[j] > d) return;
	
	for(int i = -9; i <= 9; ++ i){
		if(mmm){
		    dfs(j - 1, now + i * wjj[j], tmp * (i < 0 ? orz[-i] : otz[i]));
		}
		else{
			dfs(j - 1, now + i * wjj[j], tmp * orz[std::abs(i)]);
		}
	}
}

int main(){
	mi10[0] = 1;
	for(int i = 1; i < MAXN; ++ i) mi10[i] = mi10[i - 1] * 10ll;
	scanf("%lld", &d);
	for(int i = 2; i <= 18; ++ i){
		for(int j = i / 2, t = 1; j; -- j, ++ t){
			wjj[j] = mi10[i - t] - mi10[t - 1];
		}
		tz[0] = wjj[0];
		for(int j = 1; j <= i / 2; ++ j) tz[j] = tz[j - 1] + wjj[j];
		if(i & 1){
			dfs(i / 2, 0, 10, 1);
		}
		else{
			dfs(i / 2, 0, 1, 1);
		}
		//printf("%d complete\n", i);
	}
	printf("%lld\n", ans);
	return 0;
}
### Prompt

Please provide a Cpp coded solution 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>

#define ll long long
#define MAXN (19)

ll d;
ll mi10[MAXN], wjj[MAXN], tz[MAXN];
ll orz[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
ll otz[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
ll ans;

void dfs(int j, ll now, ll tmp, bool mmm = false){
	if(j == 0){
		if(now == d) ans += tmp;
		return;
	}
	
	if(now + 9 * tz[j] < d) return;
	if(now - 9 * tz[j] > d) return;
	
	for(int i = -9; i <= 9; ++ i){
		if(mmm){
		    dfs(j - 1, now + i * wjj[j], tmp * (i < 0 ? orz[-i] : otz[i]));
		}
		else{
			dfs(j - 1, now + i * wjj[j], tmp * orz[std::abs(i)]);
		}
	}
}

int main(){
	mi10[0] = 1;
	for(int i = 1; i < MAXN; ++ i) mi10[i] = mi10[i - 1] * 10ll;
	scanf("%lld", &d);
	for(int i = 2; i <= 18; ++ i){
		for(int j = i / 2, t = 1; j; -- j, ++ t){
			wjj[j] = mi10[i - t] - mi10[t - 1];
		}
		tz[0] = wjj[0];
		for(int j = 1; j <= i / 2; ++ j) tz[j] = tz[j - 1] + wjj[j];
		if(i & 1){
			dfs(i / 2, 0, 10, 1);
		}
		else{
			dfs(i / 2, 0, 1, 1);
		}
		//printf("%d complete\n", i);
	}
	printf("%lld\n", ans);
	return 0;
}
```