#include <iostream>
#include <cmath>

using namespace std;

long long p10[19];

long long search(long long D, int len, bool first = false){
    if(abs(D) >= p10[len]) return 0;
    if(len <= 1) return D == 0 ? p10[len] : 0;
    long long res = 0;
    for(int dif=-9;dif<=9;dif++){
        long long add = dif * p10[len-1] - dif;
        long long newD = D + add;
        if(abs(newD) % 10 != 0) continue;
        long long mul = 10 - abs(dif) - (first && dif <= 0 ? 1 : 0);
        res += mul * search(newD/10, len-2);
    }
    return res;
}

int main(){
    p10[0] = 1;
    for(int i=1;i<19;i++) p10[i] = 10 * p10[i-1];
    long long D;
    while(cin >> D){
        long long res = 0;
        for(int i=1;i<=18;i++) res += search(D, i, true);
        cout << res << endl;
    }
}
### Prompt

Please create a solution in cpp to 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 <cmath>

using namespace std;

long long p10[19];

long long search(long long D, int len, bool first = false){
    if(abs(D) >= p10[len]) return 0;
    if(len <= 1) return D == 0 ? p10[len] : 0;
    long long res = 0;
    for(int dif=-9;dif<=9;dif++){
        long long add = dif * p10[len-1] - dif;
        long long newD = D + add;
        if(abs(newD) % 10 != 0) continue;
        long long mul = 10 - abs(dif) - (first && dif <= 0 ? 1 : 0);
        res += mul * search(newD/10, len-2);
    }
    return res;
}

int main(){
    p10[0] = 1;
    for(int i=1;i<19;i++) p10[i] = 10 * p10[i-1];
    long long D;
    while(cin >> D){
        long long res = 0;
        for(int i=1;i<=18;i++) res += search(D, i, true);
        cout << res << endl;
    }
}
```