#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
ll pt[21];
int main() {
	ll d;
	cin >> d;
	ll tp = 1;
	for(int i=0;i<=20;i++) {
		pt[i] = tp;
		if(i < 18) {
			tp *= 10;
		}
	}
	ll tot = 0;
	for(int i=2;i<=20;i++) {
		ll ct = 1;
		ll b = pt[i-1]-1;
		ll dv = d;
		map<ll,ll> bs,nu;
		bs[0] = 1;
		if(i >= 18) {
			b = 0;
			for(int j=0;j<17;j++) {
				if(i-j <= 18) {
					b += 9*pt[j];
				} else {
					ll q = 10;
					if(j == 0) q--;
					bs[0] *= q;
				}
			}
		}
		for(int j=max(i-18,0);j<(i+1)/2;j++) {
			nu.clear();
			ll sub = 10;
			if(j == 0) sub--;
			for(auto& it: bs) {
				if(b > 0) {
					ll ml = ((d-it.first)/b);
					if(it.first+ml*b > d) {ml--;}
					if(abs(ml) > sub) {continue;}
					ll lb = it.first+ml*b;
					ll ub = lb+b;
					nu[lb] += max(sub-abs(ml),0LL)*it.second;
					nu[ub] += max(sub-abs(ml+1),0LL)*it.second;
					//cout << "add " << lb << ", " << ub << '\n';
				} else {
					nu[it.first] += 10*it.second;
				}
			}
			b /= 10;
			b = (b/pt[j+1])*pt[j+1];
			bs = nu;
		}
		ct = bs[d];
		tot += ct;
	}
	cout << tot << '\n';
}
### Prompt

Construct a cpp code solution to the problem outlined:

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;
typedef long long ll;
typedef vector<ll> vl;
ll pt[21];
int main() {
	ll d;
	cin >> d;
	ll tp = 1;
	for(int i=0;i<=20;i++) {
		pt[i] = tp;
		if(i < 18) {
			tp *= 10;
		}
	}
	ll tot = 0;
	for(int i=2;i<=20;i++) {
		ll ct = 1;
		ll b = pt[i-1]-1;
		ll dv = d;
		map<ll,ll> bs,nu;
		bs[0] = 1;
		if(i >= 18) {
			b = 0;
			for(int j=0;j<17;j++) {
				if(i-j <= 18) {
					b += 9*pt[j];
				} else {
					ll q = 10;
					if(j == 0) q--;
					bs[0] *= q;
				}
			}
		}
		for(int j=max(i-18,0);j<(i+1)/2;j++) {
			nu.clear();
			ll sub = 10;
			if(j == 0) sub--;
			for(auto& it: bs) {
				if(b > 0) {
					ll ml = ((d-it.first)/b);
					if(it.first+ml*b > d) {ml--;}
					if(abs(ml) > sub) {continue;}
					ll lb = it.first+ml*b;
					ll ub = lb+b;
					nu[lb] += max(sub-abs(ml),0LL)*it.second;
					nu[ub] += max(sub-abs(ml+1),0LL)*it.second;
					//cout << "add " << lb << ", " << ub << '\n';
				} else {
					nu[it.first] += 10*it.second;
				}
			}
			b /= 10;
			b = (b/pt[j+1])*pt[j+1];
			bs = nu;
		}
		ct = bs[d];
		tot += ct;
	}
	cout << tot << '\n';
}
```