Self Numbers

Time limit1sMemory limit256 MB

Summary

Print all self numbers up to 10000, that is, numbers with no generator under d(n) = n + digit sum of n.

Level: Easy3 of 10
Topics: Implementation, Math, Array, Brute force
Solved: No attempts yet

Problem

A self number is a number named in 1949 by the Indian mathematician D. R. Kaprekar. For a positive integer $n$ , define the function $d(n)$ as $n$ plus the sum of the digits of $n$ . For example, $d(75) = 75 + 7 + 5 = 87$ .

Given a positive integer $n$ , we can build the infinite sequence $n, d(n), d(d(n)), d(d(d(n))), \dots$ . For example, starting from 33 the next number is $33 + 3 + 3 = 39$ , then $39 + 3 + 9 = 51$ , then $51 + 5 + 1 = 57$ , producing the sequence:

$33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, \dots$

Here $n$ is called a generator of $d(n)$ . In the sequence above, 33 is a generator of 39, 39 is a generator of 51, and 51 is a generator of 57. A number can have more than one generator; for example, 101 has two generators, 91 and 100.

A number that has no generator is called a self number. There are 13 self numbers less than 100:

$1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97$

Write a program that prints every self number less than or equal to 10000, one per line.

Input

There is no input.

Output

Print every self number less than or equal to 10000 in increasing order, one per line.

Examples1

Example 1

Input

Expected output