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;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint d;
    cin >> d;
    if (d % 9 != 0) {
        cout << 0 << "\n";
        return 0;
    }
    d /= 9;
    lint ret = 0;
    for (int i = 1; i < 19; ++i) {
        lint t    = d;
        lint temp = 1;
        lint coef = 0;
        lint ten  = 1;
        for (int j = 0; j < i - 1; ++j) {
            coef += ten;
            ten *= 10;
        }
        for (int j = 0; j < i / 2; ++j) {
            lint tot = t % (10);
            if (j == 0)
                temp *= (9 - tot);
            else
                temp *= (10 - tot);
            t -= coef * tot;
            if (t < 0)
                t = -t;
            t /= 10;
            coef /= 100;
        }
        if (i % 2 == 1)
            temp *= 10; // 12?12, 0-9
        if (t == 0)
            ret += temp;
    }
    cout << ret << "\n";
    return 0;
}