#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
#define inf 1000000001
using namespace std;
int d,len;ll pw10[20],ad[20],ans;
void init(){
	pw10[0]=1;
	rep (i,1,18) pw10[i]=pw10[i-1]*10;
	rep (i,0,9) rep (j,0,9) ad[i-j+10]++;
}
void dfs(int k,ll now,ll ret){
	if (k>=len/2){
		if (len&1) ret*=10;
		if (now==d) ans+=ret;
		return;
	}
	int i=-9;
	while (i<=9&&now+i*(pw10[len-k-1]-pw10[k])<=d) i++;
//	if (len==2) cerr<<i<<'\n';
	i--;
	dfs(k+1,now+i*(pw10[len-k-1]-pw10[k]),ret*(ad[i+10]-(!k&&i>=0)));
	i++;
	if (i<=9) dfs(k+1,now+i*(pw10[len-k-1]-pw10[k]),ret*(ad[i+10]-(!k&&i>=0)));
}
int main(){
	init();
	cin>>d;
	for (len=1;len<=19;len++) dfs(0,0,1);
	cout<<ans<<'\n';
	return 0;
}
### Prompt

Please create a solution in cpp 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>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
#define inf 1000000001
using namespace std;
int d,len;ll pw10[20],ad[20],ans;
void init(){
	pw10[0]=1;
	rep (i,1,18) pw10[i]=pw10[i-1]*10;
	rep (i,0,9) rep (j,0,9) ad[i-j+10]++;
}
void dfs(int k,ll now,ll ret){
	if (k>=len/2){
		if (len&1) ret*=10;
		if (now==d) ans+=ret;
		return;
	}
	int i=-9;
	while (i<=9&&now+i*(pw10[len-k-1]-pw10[k])<=d) i++;
//	if (len==2) cerr<<i<<'\n';
	i--;
	dfs(k+1,now+i*(pw10[len-k-1]-pw10[k]),ret*(ad[i+10]-(!k&&i>=0)));
	i++;
	if (i<=9) dfs(k+1,now+i*(pw10[len-k-1]-pw10[k]),ret*(ad[i+10]-(!k&&i>=0)));
}
int main(){
	init();
	cin>>d;
	for (len=1;len<=19;len++) dfs(0,0,1);
	cout<<ans<<'\n';
	return 0;
}
```