#include <bits/stdc++.h>
using namespace std;
long long ans=0,pw[20],d,cur;
long long bt(long long now,int rem,int dg){
	if(rem==0) return (now==0);
	if(rem==1) return (now==0)*10LL;
	long long prd=pw[dg-1]-pw[cur-dg];
	long long mul=now/prd,ret=0;
	if(rem==dg){
		ret+=1LL*max(0LL,9-abs(mul))*bt(now-prd*mul,rem-2,dg-1);
		if(mul<0) mul--;
		else if(mul==0) mul++, ret+=1LL*max(0LL,9-abs(mul))*bt(now-prd*mul,rem-2,dg-1), mul-=2;
		else mul++;
		ret+=1LL*max(0LL,9-abs(mul))*bt(now-prd*mul,rem-2,dg-1);
	}
	else{
		ret+=1LL*max(0LL,10-abs(mul))*bt(now-prd*mul,rem-2,dg-1);
		if(mul<0) mul--;
		else if(mul==0) mul++, ret+=1LL*max(0LL,10-abs(mul))*bt(now-prd*mul,rem-2,dg-1), mul-=2;
		else mul++;
		ret+=1LL*max(0LL,10-abs(mul))*bt(now-prd*mul,rem-2,dg-1);
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin>>d;
	pw[0]=1;
	for(int i=1;i<=18;i++) pw[i]=pw[i-1]*10LL;
	for(int i=1;i<=19;i++) cur=i, ans+=bt(d,i,i);
	cout<<ans;
}

### 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 <bits/stdc++.h>
using namespace std;
long long ans=0,pw[20],d,cur;
long long bt(long long now,int rem,int dg){
	if(rem==0) return (now==0);
	if(rem==1) return (now==0)*10LL;
	long long prd=pw[dg-1]-pw[cur-dg];
	long long mul=now/prd,ret=0;
	if(rem==dg){
		ret+=1LL*max(0LL,9-abs(mul))*bt(now-prd*mul,rem-2,dg-1);
		if(mul<0) mul--;
		else if(mul==0) mul++, ret+=1LL*max(0LL,9-abs(mul))*bt(now-prd*mul,rem-2,dg-1), mul-=2;
		else mul++;
		ret+=1LL*max(0LL,9-abs(mul))*bt(now-prd*mul,rem-2,dg-1);
	}
	else{
		ret+=1LL*max(0LL,10-abs(mul))*bt(now-prd*mul,rem-2,dg-1);
		if(mul<0) mul--;
		else if(mul==0) mul++, ret+=1LL*max(0LL,10-abs(mul))*bt(now-prd*mul,rem-2,dg-1), mul-=2;
		else mul++;
		ret+=1LL*max(0LL,10-abs(mul))*bt(now-prd*mul,rem-2,dg-1);
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin>>d;
	pw[0]=1;
	for(int i=1;i<=18;i++) pw[i]=pw[i-1]*10LL;
	for(int i=1;i<=19;i++) cur=i, ans+=bt(d,i,i);
	cout<<ans;
}

```