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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;

ll d;
ll p[20];
int dx1[20], dx2[20];
vector<ll> v;

void dfs(int s, int e, vector<pi> &w, ll val, ll cnt){
	if(s == e){
		w.push_back(pi(-val, cnt));
		return;
	}
	for(int i=-9; i<=9; i++){
		dfs(s+1, e, w, val + i * v[s], cnt * (s == 0 ? dx2[i + 10] : dx1[i + 10]));
	}
}

ll solve(int l){
	v.clear();
	for(int i=0; l-1-i > i; i++){
		v.push_back(p[l-1-i] - p[i]);
	}
	vector<pi> v1, v2;
	dfs(0, (v.size()+1) / 2, v1, 0, 1);
	dfs((v.size()+1) / 2, v.size(), v2, 0, 1);
	ll ans = 0;
	map<ll, ll> mp;
	for(auto &i : v2) mp[i.first] += i.second;
	for(auto &i : v1){
		ans += mp[d-i.first] * i.second;
	}	
	if(l % 2 == 1) ans *= 10;
	return ans;
}

int main(){
	p[0] = 1;
	for(int i=1; i<20; i++) p[i] = p[i-1] * 10;
	for(int i=0; i<10; i++){
		for(int j=0; j<10; j++){
			dx1[i-j+10]++;
		}
	}
	for(int i=1; i<10; i++){
		for(int j=0; j<10; j++){
			dx2[i-j+10]++;
		}
	}
	cin >> d;
	ll ans = 0;
	for(int i=2; i<=18; i++) ans += solve(i);
	cout << ans << endl;
}
