eolymp
bolt
Try our new interface for solving problems
Problems

X + R(X) = N

X + R(X) = N

Time limit 0.75 seconds
Memory limit 256 MiB

Ruslan is crazy about counting numbers and solving problems. His favourite pastime is to make up a problem and solve it by himself. Some time ago he heard about a very interesting problem: given the positive integer N, you have to say whether such X that X + R(X) = N exists or not, where X is a positive integer, and R(X) is the number X written backwards. Then, Ruslan has decided that this task is elementary, so he didn't start solving it, but made up a more difficult problem instead.

You are given the positive integer number N. How many positive integer numbers X are there, that X + R(X) = N?

R(X) is the number X written backwards. For example: R(123) = 321R(150) = 51.

Input data

Input will consist of multiple test cases. Each case will be a single line containing number N (1N10^10000). A line with a single zero terminates the input.

Maximum size of input is 200000 bytes.

Output data

Output for each test case should consist of a single integer on a line, indicating the number of numbers X satisfying the condition. Do not output leading zeros.

Examples

Input example #1
1
2
11
13
14003
767513456469789456166547987979741366664879441
0
Output example #1
0
1
1
0
60
0
Source Izhevsk STU Contest, Petrozavodsk training camp, February 6, 2009