Once, Beremiz explained to the Caliph of Baghdad:

*“Let us consider the numbers 220 and 284.
The divisors of 220 that are positive and less than 220
are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, and their sum is 284.
The divisors of 284 that are positive and less than 284
are 1, 2, 4, 71 and 142, and their sum is 220.
From this relationship, mathematicians concluded
that 220 and 284 are amicable,
because each one seems to honor the other.*”

Input

Input consists of at most 10^{4} natural numbers n
between 1 and 10^{8}.

Output

For every natural number n, let s(n) be the sum of the positive divisors of n that are less than n. Consider the sequence n, s(n), s(s(n)), s(s(s(n))), … If n is amicable, the sequence is cyclic with period 2 from its beginning. For example, for n = 220 we have 220, 284, 220, … If n is perfect, the sequence is cyclic with period 1 from the beginning. For example, for n = 6 we have 6, 6, …

Generalizing, these are the three possible situations:
(i) The sequence reaches a cycle (with period 1, 2 or greater)
after zero or more steps.
(ii) The sequence reaches 1.
Taking into account that s(1) = 0, we stop the sequence.
(iii) The sequence grows a lot,
to the point of not knowing whether we would reach a cycle sometime
or if it tends to infinity.
In this problem, we will arbitrarily stop the sequence
anytime it exceeds 10^{8}.

For every given n,
print one line with the first terms of the sequence,
stopping when some number would repeat, when we reach 1,
or when we reach a number larger than 10^{8}.

Public test cases

**Input**

220 284 6 1 9 105086 115560 100000000

**Output**

220 284 284 220 6 1 9 4 3 1 105086 52546 36158 18922 9464 12496 14288 15472 14536 14264 115560 273240 763560 2174040 5928120 15671880 44615160 100385280 100000000 149511591

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Spanish
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++