题目描述

所谓 H 数，是指该数除 $1$ 以外最多只有 $2,3,5,7$ 四种素因子。换句话说，其所有素因子只能来自集合 $\{2,3,5,7\}$。例如 $630$ 的素因子有 $2,3,5,7$，因此是 H 数；而 $22$ 有素因子 $11$，不是 H 数。特别地，$1$ 也被认为是 H 数。

现在给定一个正整数 $n$，请你求出从小到大排列的第 $n$ 个 H 数。如 $n=30$，应输出 $49$。规定所求的 H 数不超出长整型数范围。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示第 $n$ 个 H 数。

1

1

30

49

数据范围与提示

• $1 \le n \le 4000$。
• 保证结果在 long long 范围内。