#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

const int L = 18;

s64 delta;
s64 prePow[L + 1];

s64 solve(int l, bool first, s64 delta)
{
	if (abs(delta) >= prePow[l])
		return 0;
	if (l <= 1)
		return l ? (delta ? 0 : 10) : 1;

	s64 res = 0;
	s64 pow = prePow[l - 1] - 1;
	for (int d = -9; d <= 9; ++d)
		if ((delta - d * pow) % 10 == 0)
			res += solve(l - 2, false, (delta - d * pow) / 10) * (10 - abs(d) - first);

	return res;
}

int main()
{
	cin >> delta;

	prePow[0] = 1;
	for (int i = 1; i <= L; ++i)
		prePow[i] = prePow[i - 1] * 10;

	s64 res = 0;
	for (int i = 1; i <= L; ++i)
		res += solve(i, true, delta);

	cout << res << endl;

	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

const int L = 18;

s64 delta;
s64 prePow[L + 1];

s64 solve(int l, bool first, s64 delta)
{
	if (abs(delta) >= prePow[l])
		return 0;
	if (l <= 1)
		return l ? (delta ? 0 : 10) : 1;

	s64 res = 0;
	s64 pow = prePow[l - 1] - 1;
	for (int d = -9; d <= 9; ++d)
		if ((delta - d * pow) % 10 == 0)
			res += solve(l - 2, false, (delta - d * pow) / 10) * (10 - abs(d) - first);

	return res;
}

int main()
{
	cin >> delta;

	prePow[0] = 1;
	for (int i = 1; i <= L; ++i)
		prePow[i] = prePow[i - 1] * 10;

	s64 res = 0;
	for (int i = 1; i <= L; ++i)
		res += solve(i, true, delta);

	cout << res << endl;

	return 0;
}
```