H数

题目背景

题目描述

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

输入输出格式

输入格式


一个数n(如题目)

输出格式


第n个H数

输入输出样例

输入样例 #1

30

输出样例 #1

49

输入样例 #2

1

输出样例 #2

1

说明

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