Amicable numbers P65796

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⁴ natural numbers n between 1 and 10⁸.

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⁸.

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⁸.