#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll bs[20];
ll D, f0[20], f[20];
ll a[20], an, ans;
void dfs(int x, ll v, ll c)
{
	if(x == an)
	{
		ans += (v == D) * c;
		return;
	}
	if(abs(v - D) > a[x] * 20)return;
	for(int i = 0; i < 20; i ++)
	{
		int cnt;
		if(!x) cnt = f0[i];
		else cnt = f[i];
		if(!a[x])cnt = i < 10;
		if(!cnt) continue;
		dfs(x + 1, v + (i - 10) * a[x], c * cnt);
	}
}
void solve(int n)
{
	an = 0;
	for(int i = 0; i < n; i ++)
	{
		if(i > n - i - 1)break;
		a[an ++] = bs[n - i - 1] - bs[i];
	}
	dfs(0, 0, 1);
}
int main()
{
	for(int i = 0; i <= 9; i ++)
		for(int j = 0; j <= 9; j ++)
			f[i - j + 10] ++;
 
	for(int i = 0; i <= 9; i ++)
		for(int j = 1; j <= 9; j ++)
			f0[i - j + 10] ++;
 
	bs[0] = 1;
	for(int i = 1; i < 19; i ++)
        bs[i] = bs[i - 1] * 10;
	cin >> D;
	for(int i = 1; i <= 19; i ++)
		solve(i);
	cout<<ans<<endl;
	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 <bits/stdc++.h>
#define ll long long
using namespace std;
ll bs[20];
ll D, f0[20], f[20];
ll a[20], an, ans;
void dfs(int x, ll v, ll c)
{
	if(x == an)
	{
		ans += (v == D) * c;
		return;
	}
	if(abs(v - D) > a[x] * 20)return;
	for(int i = 0; i < 20; i ++)
	{
		int cnt;
		if(!x) cnt = f0[i];
		else cnt = f[i];
		if(!a[x])cnt = i < 10;
		if(!cnt) continue;
		dfs(x + 1, v + (i - 10) * a[x], c * cnt);
	}
}
void solve(int n)
{
	an = 0;
	for(int i = 0; i < n; i ++)
	{
		if(i > n - i - 1)break;
		a[an ++] = bs[n - i - 1] - bs[i];
	}
	dfs(0, 0, 1);
}
int main()
{
	for(int i = 0; i <= 9; i ++)
		for(int j = 0; j <= 9; j ++)
			f[i - j + 10] ++;
 
	for(int i = 0; i <= 9; i ++)
		for(int j = 1; j <= 9; j ++)
			f0[i - j + 10] ++;
 
	bs[0] = 1;
	for(int i = 1; i < 19; i ++)
        bs[i] = bs[i - 1] * 10;
	cin >> D;
	for(int i = 1; i <= 19; i ++)
		solve(i);
	cout<<ans<<endl;
	return 0;
}
```