#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

int cnt[20];
LL pw[20];
LL ans;
int D,len;

void pre()
{
	for (int D_=D;D_;D_/=10,++len);
	for (int i=0;i<10;++i)
		for (int j=0;j<10;++j)
			++cnt[i-j+10];
	pw[0]=1;
	for (int i=1;i<=len<<1;++i) pw[i]=10ll*pw[i-1];
}

void dfs(int L,int idx=1,LL cur=0,LL ways=1)
{
	if ((idx<<1)>L)
	{
		if (cur==D) ans+=(L&1?10ll:1ll)*ways;
		return;
	}
	for (int d=-9;d<10;++d)
	{
		LL nxt=cur+d*(pw[L-idx]-pw[idx-1]);
		if (D%pw[idx]==((nxt%pw[idx])+pw[idx])%pw[idx]) dfs(L,idx+1,nxt,ways*(cnt[d+10]-(idx==1)));
	}
}

int main()
{
	//freopen("mirrored.in","r",stdin),freopen("mirrored.out","w",stdout);
	scanf("%d",&D),pre();
	for (int i=len;i<=len<<1;++i) dfs(i);
	printf("%lld\n",ans);
	//fclose(stdin),fclose(stdout);
	return 0;
}
### Prompt

Generate a cpp solution 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 <cstdio>

using namespace std;

typedef long long LL;

int cnt[20];
LL pw[20];
LL ans;
int D,len;

void pre()
{
	for (int D_=D;D_;D_/=10,++len);
	for (int i=0;i<10;++i)
		for (int j=0;j<10;++j)
			++cnt[i-j+10];
	pw[0]=1;
	for (int i=1;i<=len<<1;++i) pw[i]=10ll*pw[i-1];
}

void dfs(int L,int idx=1,LL cur=0,LL ways=1)
{
	if ((idx<<1)>L)
	{
		if (cur==D) ans+=(L&1?10ll:1ll)*ways;
		return;
	}
	for (int d=-9;d<10;++d)
	{
		LL nxt=cur+d*(pw[L-idx]-pw[idx-1]);
		if (D%pw[idx]==((nxt%pw[idx])+pw[idx])%pw[idx]) dfs(L,idx+1,nxt,ways*(cnt[d+10]-(idx==1)));
	}
}

int main()
{
	//freopen("mirrored.in","r",stdin),freopen("mirrored.out","w",stdout);
	scanf("%d",&D),pre();
	for (int i=len;i<=len<<1;++i) dfs(i);
	printf("%lld\n",ans);
	//fclose(stdin),fclose(stdout);
	return 0;
}
```