Description

对于一个数字x,定义s(x)为x的各位数字之和。

例如$s(123)=1+2+3=6$

定义一个数为异数

当且仅当任意$y>x$都满足$y/S(y)⩾x/S(x)$

求前k个Snuke Number。

Format

Input

第一行给出K

K<=10^5

Output

如题

Samples

10

1
2
3
4
5
6
7
8
9
19