Background

Description

对于一个整数n，定义f(n)为n的各位数字之和，求f(f(x))=y（y为输入值，1<=y<=30）的最小自然数x是多少

注：注意性能。

Format

Input

Output

Samples

15

69999999

20

2999999999999999999999999999999999

18

99999999999

Limitation

1s, 1024KiB for each test case.