Background

Special for beginners, ^_^

Description

所谓 $H$ 数，是指只含有 $2,3,5,7$ 这些质因数的数，如 $630$ 是 $H$ 数，而 $22$ 不是。现在要求输出第 $n$ 个 $H$ 数，为了方便起见将 $H[1]$ 定为 $1$。已知 $1\le n\le 10000$，最后数据在 $int64$ 范围之内。

Format

Input

一个数 $n$（如题目）。

Output

第 $n$ 个 $H$ 数。

Samples

30

49

1

1

Hint

穷举会爆掉，要用生成法，最好加优化，不然空间复杂度比较大

Limitation

1s, 1024KiB for each test case.