#include <set>
#include <map>
#include <cmath> 
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
LL dd,Ans,p[20];
LL dfs(LL l,LL r,LL d){
	if(l>=r){
		if(d==0)return l==r?10:1;
		return 0;
	}
	if(d%10==0){
		if(l!=1)return 10*dfs(l+1,r-1,d/10);
		return 9*dfs(l+1,r-1,d/10); 
	}
	LL D=d%10-10;
	LL next=d-D+D*p[r-l];
	if(l==1)return (9+D)*dfs(l+1,r-1,abs(next)/10);
	return (10+D)*dfs(l+1,r-1,abs(next)/10); 
} 
int main() {
	scanf("%lld",&dd);
	p[0]=1;
	for(int i=1;i<=18;i++)p[i]=p[i-1]*10;
	for(int i=2;i<=18;i++)
		Ans+=dfs(1,i,dd);
	printf("%lld",Ans);
    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 <set>
#include <map>
#include <cmath> 
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
LL dd,Ans,p[20];
LL dfs(LL l,LL r,LL d){
	if(l>=r){
		if(d==0)return l==r?10:1;
		return 0;
	}
	if(d%10==0){
		if(l!=1)return 10*dfs(l+1,r-1,d/10);
		return 9*dfs(l+1,r-1,d/10); 
	}
	LL D=d%10-10;
	LL next=d-D+D*p[r-l];
	if(l==1)return (9+D)*dfs(l+1,r-1,abs(next)/10);
	return (10+D)*dfs(l+1,r-1,abs(next)/10); 
} 
int main() {
	scanf("%lld",&dd);
	p[0]=1;
	for(int i=1;i<=18;i++)p[i]=p[i-1]*10;
	for(int i=2;i<=18;i++)
		Ans+=dfs(1,i,dd);
	printf("%lld",Ans);
    return 0;
}
```