#include<cstdio>
typedef long long ll;
ll pw[20];
ll dfs(int l,int r,ll d){
	if(l>r)return!d;
	if(l==r)return d?0:10;
	ll k=pw[r]-pw[l],t=d/k,s=0;
	if(t<10)s+=dfs(l+1,r-1,d-k*t)*(10-t-!l);
	if(t+1<10)s+=dfs(l+1,r-1,k*t+k-d)*(9-t-!l);
	return s;
}
int main(){
	int D;scanf("%d",&D);
	ll ans=0;
	for(int i=*pw=1;i<=18;i++){
		pw[i]=pw[i-1]*10;
		ans+=dfs(0,i,D);
	}
	printf("%lld\n",ans);
} 
### Prompt

Please formulate 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<cstdio>
typedef long long ll;
ll pw[20];
ll dfs(int l,int r,ll d){
	if(l>r)return!d;
	if(l==r)return d?0:10;
	ll k=pw[r]-pw[l],t=d/k,s=0;
	if(t<10)s+=dfs(l+1,r-1,d-k*t)*(10-t-!l);
	if(t+1<10)s+=dfs(l+1,r-1,k*t+k-d)*(9-t-!l);
	return s;
}
int main(){
	int D;scanf("%d",&D);
	ll ans=0;
	for(int i=*pw=1;i<=18;i++){
		pw[i]=pw[i-1]*10;
		ans+=dfs(0,i,D);
	}
	printf("%lld\n",ans);
} 
```