#include <cstdio>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

typedef long long LL;
int n;
LL pow10[20],ans;

void dfs(int n,int k,LL sum,int cnt)
{
    if (sum%pow10[k])
        return;
    if (k>(n-1)/2)
    {
        if (!sum)
            ans+=n&1?cnt:cnt*10;
        return;
    }
    dfs(n,k+1,sum,k?cnt*10:cnt*9);
    repu(i,1,9)
    {
        dfs(n,k+1,sum+i*(pow10[n-k]-pow10[k]),cnt*(k?10-i:9-i));
        dfs(n,k+1,sum-i*(pow10[n-k]-pow10[k]),cnt*(k?10-i:9-i));
    }
}

int main()
{
    scanf("%d",&n),pow10[0]=1;
    repu(i,1,17)
        pow10[i]=pow10[i-1]*10;
    repu(i,1,17)
        dfs(i,0,n,1);
    printf("%lld\n",ans);
    return 0;
}
### Prompt

In CPP, your task is to solve 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 <cstdio>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

typedef long long LL;
int n;
LL pow10[20],ans;

void dfs(int n,int k,LL sum,int cnt)
{
    if (sum%pow10[k])
        return;
    if (k>(n-1)/2)
    {
        if (!sum)
            ans+=n&1?cnt:cnt*10;
        return;
    }
    dfs(n,k+1,sum,k?cnt*10:cnt*9);
    repu(i,1,9)
    {
        dfs(n,k+1,sum+i*(pow10[n-k]-pow10[k]),cnt*(k?10-i:9-i));
        dfs(n,k+1,sum-i*(pow10[n-k]-pow10[k]),cnt*(k?10-i:9-i));
    }
}

int main()
{
    scanf("%d",&n),pow10[0]=1;
    repu(i,1,17)
        pow10[i]=pow10[i-1]*10;
    repu(i,1,17)
        dfs(i,0,n,1);
    printf("%lld\n",ans);
    return 0;
}
```