#include <bits/stdc++.h>
using namespace std;

typedef long long  LL;
int d,n,m,ans;
LL a[20],s[20];

void dfs(int x,LL d,int cnt)
{
	if (x>m)  {ans+=cnt*(n&1?10:1);  return;}
	for (int i=-9; i<=9; i++)
		if ((-9*s[x+1]<=d-i*a[x])&&(d-i*a[x]<=9*s[x+1]))
			dfs(x+1,d-i*a[x],cnt*(10-abs(i)-(x==1)*(i>=0)));
}

void work()
{
	scanf("%d",&d);
	for (n=2; n<20; n++)
		{
			LL x=1,y=1;
			m=n/2;
			for (int i=1; i<n; i++)  x*=10;
			for (int i=1; i<=m; i++)  a[i]=x-y,x/=10,y*=10;
			for (int i=m; i; i--)  s[i]=s[i+1]+a[i];
			dfs(1,d,1);
		}
	printf("%d",ans);
}

int main()
{
	work();
	return 0;
}

### Prompt

Create a solution in cpp for 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;
int d,n,m,ans;
LL a[20],s[20];

void dfs(int x,LL d,int cnt)
{
	if (x>m)  {ans+=cnt*(n&1?10:1);  return;}
	for (int i=-9; i<=9; i++)
		if ((-9*s[x+1]<=d-i*a[x])&&(d-i*a[x]<=9*s[x+1]))
			dfs(x+1,d-i*a[x],cnt*(10-abs(i)-(x==1)*(i>=0)));
}

void work()
{
	scanf("%d",&d);
	for (n=2; n<20; n++)
		{
			LL x=1,y=1;
			m=n/2;
			for (int i=1; i<n; i++)  x*=10;
			for (int i=1; i<=m; i++)  a[i]=x-y,x/=10,y*=10;
			for (int i=m; i; i--)  s[i]=s[i+1]+a[i];
			dfs(1,d,1);
		}
	printf("%d",ans);
}

int main()
{
	work();
	return 0;
}

```