Background

Special for beginners, ^_^

Description

一个自然数，把它的每位数字取下来相乘，得到一个新的自然数，不断地进行这种操作，直到这个数变成一位数。 例如，49->36->18->8。所以49需要进行3次操作。 问经过n次操作的最小自然数是多少。

Format

Input

每行输入一个n（不超过11），表示操作次数。

Output

每行输出一个n对应的最小自然数。

Samples

1
2

10
25

Limitation

1s, 1024KiB for each test case.