#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dig[20];

ll dfs(int l,int r,ll d){
  if(l<=r) return d ? 0 : ((l==r)?10:1);
  ll t=(10-d%10)%10;
  ll v=d-dig[l-r]*t+t;
  return ((r?10:9)-t)*dfs(l-1,r+1,llabs(v)/10);
}

int countDigit(ll d){
  if(!d) return 0;
  return 1 + countDigit(d/10);
}

int countZero(ll d){
  if(d%10) return 0;
  return 1+countZero(d/10);
}

int main(){
  dig[0]=1;
  for(int i=1;i<19;i++)
    dig[i] = dig[i-1]*10;
  ll d;
  cin>>d;
  int cd=countDigit(d);
  int cz=countZero(d);
  ll ans = 0;
  for(int i=1;i<=cd*2;i++) {
    ans += dfs(i,0,d);
    //cout<<ans<<endl;
  }
  //cout<<endl;
  cout<<ans<<endl;
  return 0;
}

### 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dig[20];

ll dfs(int l,int r,ll d){
  if(l<=r) return d ? 0 : ((l==r)?10:1);
  ll t=(10-d%10)%10;
  ll v=d-dig[l-r]*t+t;
  return ((r?10:9)-t)*dfs(l-1,r+1,llabs(v)/10);
}

int countDigit(ll d){
  if(!d) return 0;
  return 1 + countDigit(d/10);
}

int countZero(ll d){
  if(d%10) return 0;
  return 1+countZero(d/10);
}

int main(){
  dig[0]=1;
  for(int i=1;i<19;i++)
    dig[i] = dig[i-1]*10;
  ll d;
  cin>>d;
  int cd=countDigit(d);
  int cz=countZero(d);
  ll ans = 0;
  for(int i=1;i<=cd*2;i++) {
    ans += dfs(i,0,d);
    //cout<<ans<<endl;
  }
  //cout<<endl;
  cout<<ans<<endl;
  return 0;
}

```