#include<bits/stdc++.h>
using namespace std;
int D,ans;
long long pw[20];
void DFS(int tot,int pos,long long res,long long ti){
	//cerr<<tot<<" "<<pos<<" "<<res<<endl;
	if(pw[pos+1]<=res||-pw[pos+1]>=res) return;
	if(pos<=tot/2){
		if(pos*2==tot) ti*=10;
		if(res==0) ans+=ti;
		return;
	}
	for(int i=-9;i<=9;i++){
		DFS(tot,pos-1,res+i*(pw[pos]-pw[tot-pos]),ti*(10-abs(i)-(pos==tot&&i<=0? 1:0)));
	}
}
int main(){
	cin>>D;pw[0]=1;
	for(int i=1;i<=19;i++) pw[i]=pw[i-1]*10;
	for(int i=0;i<=18;i++)
		DFS(i,i,D,1);
	cout<<ans<<endl;
	return 0;
}
### Prompt

Generate 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;
int D,ans;
long long pw[20];
void DFS(int tot,int pos,long long res,long long ti){
	//cerr<<tot<<" "<<pos<<" "<<res<<endl;
	if(pw[pos+1]<=res||-pw[pos+1]>=res) return;
	if(pos<=tot/2){
		if(pos*2==tot) ti*=10;
		if(res==0) ans+=ti;
		return;
	}
	for(int i=-9;i<=9;i++){
		DFS(tot,pos-1,res+i*(pw[pos]-pw[tot-pos]),ti*(10-abs(i)-(pos==tot&&i<=0? 1:0)));
	}
}
int main(){
	cin>>D;pw[0]=1;
	for(int i=1;i<=19;i++) pw[i]=pw[i-1]*10;
	for(int i=0;i<=18;i++)
		DFS(i,i,D,1);
	cout<<ans<<endl;
	return 0;
}
```