Rounding Many Ways

Interview

Time limit1sMemory limit1024 MB

Summary

Given N, list every X of the form 2^a * 5^b that divides N, since X must divide both 10^Z and N.

Level: Easy3 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

Timothy and Alex had hoped to run for the UCF Student Government Association, but they realized their campaign ticket would not be alliterative, and that ended the plan. Instead, they decided to analyze statistics from many polls given to students to find which pair of programming team members would be best positioned to win the election.

The problem is that every statistic has been rounded. This would not be a problem if the pollsters had said how the numbers were rounded, but they did not. (Math note: if 198 is rounded to 200, then 198 is called the "true value" and 200 is called the "rounded value".)

For example, the rounded value 750 could come from a true value rounded to the nearest 10, or to the nearest 250. It could also come from a true value rounded to the nearest 1, which means no rounding at all. So the true value could be 625, or something close like 748.

Luckily, after some reconnaissance, Timothy and Alex found the general rounding method the pollsters used:

The original statistic is a positive integer S.
A positive integer X is chosen such that X divides some power of 10. That is, there are non-negative integers Y and Z with $X \times Y = 10^Z$ .
Finally, S is rounded to the nearest positive multiple of X to get the rounded value N. That is, there is a positive integer W with $X \times W = N$ , and $|S - N|$ is minimized.

Given the rounded value N, find every way it could have been rounded. In other words, find all values of X that satisfy both of these equations:

$X \times Y = 10^Z$
$X \times W = N$

Input

The first and only line of input contains an integer N (1 ≤ N ≤ 10^{18}), the rounded value.

Output

First print a single line with the number of different X values that N could have been derived from. Then print all of these X values in increasing order, one per line.

Hint

The explanation below covers the first sample input and output.

Output: 1
    X = 1, Y = 10, Z = 1, W = 30
    Rounded to the nearest multiple of 1: 1*10=10, 1*30=30
Output: 2
    X = 2, Y = 5, Z = 1, W = 15
    Rounded to the nearest multiple of 2: 2*5=10, 2*15=30
Output: 5
    X = 5, Y = 2, Z = 1, W = 6
    Rounded to the nearest multiple of 5: 5*2=10, 5*6=30
Output: 10
    X = 10, Y = 1, Z = 1, W = 3
    Rounded to the nearest multiple of 10: 10*1=10, 10*3=30

Examples3

Example 1
Input
```
30
```
Expected output
```
4
1
2
5
10
```
Example 2
Input
```
120
```
Expected output
```
8
1
2
4
5
8
10
20
40
```
Example 3
Input
```
8
```
Expected output
```
4
1
2
4
8
```