题目背景

小明是一所学校的数学老师，最近在讲授数论中的「无平方因子数」概念。下课时一个学生跑来问他：「老师，第 $n$ 个无平方因子数到底是多少呀？」小明一时答不上来，因为当 $n$ 很大时，人工列举并不现实。请你帮小明写一个程序，快速地求出第 $n$ 个无平方因子数。

题目描述

一个正整数被称为无平方因子数（squarefree number），当且仅当它不被任何大于 $1$ 的完全平方数整除。例如前几个无平方因子数为：

$$1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, \dots$$

注意 $4$ 不是（被 $4=2^2$ 整除），$8$ 不是（被 $4$ 整除），$9$ 也不是（被 $9$ 整除），而 $6 = 2\times 3$ 是无平方因子数。

给定正整数 $n$，请输出第 $n$ 小的无平方因子数。注意：本题采用 1-indexed 编号，即 $n=1$ 时应返回最小的无平方因子数 $1$。

输入格式

一行一个正整数 $n$。

输出格式

一行一个整数，表示第 $n$ 小的无平方因子数。

样例

样例 1

输入：

1

输出：

1

样例 2

输入：

13

输出：

19

样例 3

输入：

1000000000

输出：

1644934081

数据范围与约定

• $1 \le n \le 1\,000\,000\,000$。
• 保证答案不超过 $2 \times 10^9$，可以使用 32 位带符号整数（int）存储。