#include <cstdio>
long long D, P10[19], O;
long long DFS(int len, bool first, long long need)
{
	if (len == 0)
		return need == 0;
	if (len == 1)
		return need == 0 ? 10 - first : 0;
	long long S = 0;
	for (long long dif = -9; dif <= 9; dif++)
		if ((need - dif * (P10[len - 1] - 1)) % 10 == 0)
			S += DFS(len - 2, false, (need - dif * (P10[len - 1] - 1)) / 10) * (10 - (dif < 0 ? -dif : dif) - (first && dif >= 0));
	return S;
}
int main()
{
	scanf("%lld", &D);
	P10[0] = 1;
	for (int i = 1; i <= 18; i++)
		P10[i] = P10[i - 1] * 10;
	for (int i = 1; i <= 18; i++)
		O += DFS(i, true, D);
	printf("%lld\n", O);
	return 0;
}

### Prompt

Develop a solution in Cpp 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 <cstdio>
long long D, P10[19], O;
long long DFS(int len, bool first, long long need)
{
	if (len == 0)
		return need == 0;
	if (len == 1)
		return need == 0 ? 10 - first : 0;
	long long S = 0;
	for (long long dif = -9; dif <= 9; dif++)
		if ((need - dif * (P10[len - 1] - 1)) % 10 == 0)
			S += DFS(len - 2, false, (need - dif * (P10[len - 1] - 1)) / 10) * (10 - (dif < 0 ? -dif : dif) - (first && dif >= 0));
	return S;
}
int main()
{
	scanf("%lld", &D);
	P10[0] = 1;
	for (int i = 1; i <= 18; i++)
		P10[i] = P10[i - 1] * 10;
	for (int i = 1; i <= 18; i++)
		O += DFS(i, true, D);
	printf("%lld\n", O);
	return 0;
}

```