#include <cstdlib>
#include <cstdio>
long long pw[20];
long long calc(long long d,int b,int p){
	if (abs(d)>=pw[b]) return 0;
	if (!b) return 1;
	if (b==1) return d?0:10;
	long long x=pw[b-1]-1,v=0;
	for (int i=-9;i<=9;i++)
		if ((d-i*x)%10==0)
			v+=calc((d-i*x)/10,b-2,0)*(10-abs(i)-p);
	return v;
}
int main(){
	int D;
	scanf("%d",&D);
	pw[0]=1;
	for (int i=1;i<=18;i++) pw[i]=pw[i-1]*10ll;
	long long ans=0;
	for (int i=1;i<=18;i++) ans+=calc(D,i,1);
	printf("%lld\n",ans);
}
### Prompt

Your challenge is to write 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 <cstdlib>
#include <cstdio>
long long pw[20];
long long calc(long long d,int b,int p){
	if (abs(d)>=pw[b]) return 0;
	if (!b) return 1;
	if (b==1) return d?0:10;
	long long x=pw[b-1]-1,v=0;
	for (int i=-9;i<=9;i++)
		if ((d-i*x)%10==0)
			v+=calc((d-i*x)/10,b-2,0)*(10-abs(i)-p);
	return v;
}
int main(){
	int D;
	scanf("%d",&D);
	pw[0]=1;
	for (int i=1;i<=18;i++) pw[i]=pw[i-1]*10ll;
	long long ans=0;
	for (int i=1;i<=18;i++) ans+=calc(D,i,1);
	printf("%lld\n",ans);
}
```