#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define pb push_back
#define fr first
#define sc second

ll POW[20];
void init(){
	POW[0] = 1;
	for(int i = 1 ; i < 20 ; i ++){
		POW[i] = POW[i-1]*10;
	}
}

int keta(ll x){
	if(x == 0)return 0;
	return keta(x/10)+1;
}

ll sol(ll D,int l,ll ret,bool t){
	//cout << D << " " << l << " " << ret << endl;
	if(l == 0)return (D==0)?ret:0;
	if(l == 1)return (D==0)?(ret*10):0;
	int k = keta(abs(D));
	if(k > l)return 0;
	ll d = (10+D%10); if(d >= 10)d -= 10;
	if(d == 0)return sol(D/10,l-2,ret*(t?9:10),false);
	ll T = POW[l-1]-1;
	return sol((D-(10-d)*T)/10,l-2,ret*d,false) + sol((D+d*T)/10,l-2,ret*(t?(9-d):(10-d)),false);
}

int main(){
	init();
	
	ll D;
	cin >> D;
	
	ll ret = 0;
	int k = keta(D);
	for(int l = k ; l <= 2*k ; l ++){
		ret += sol(-D,l,1,true);
	}
	cout << ret << endl;
}


### Prompt

Create a solution in Cpp for 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<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define pb push_back
#define fr first
#define sc second

ll POW[20];
void init(){
	POW[0] = 1;
	for(int i = 1 ; i < 20 ; i ++){
		POW[i] = POW[i-1]*10;
	}
}

int keta(ll x){
	if(x == 0)return 0;
	return keta(x/10)+1;
}

ll sol(ll D,int l,ll ret,bool t){
	//cout << D << " " << l << " " << ret << endl;
	if(l == 0)return (D==0)?ret:0;
	if(l == 1)return (D==0)?(ret*10):0;
	int k = keta(abs(D));
	if(k > l)return 0;
	ll d = (10+D%10); if(d >= 10)d -= 10;
	if(d == 0)return sol(D/10,l-2,ret*(t?9:10),false);
	ll T = POW[l-1]-1;
	return sol((D-(10-d)*T)/10,l-2,ret*d,false) + sol((D+d*T)/10,l-2,ret*(t?(9-d):(10-d)),false);
}

int main(){
	init();
	
	ll D;
	cin >> D;
	
	ll ret = 0;
	int k = keta(D);
	for(int l = k ; l <= 2*k ; l ++){
		ret += sol(-D,l,1,true);
	}
	cout << ret << endl;
}


```