题目描述

一个正整数 $k$ 被称为 squarefree,如果它没有一个 $D^2(D>1)$ 这样的约数。

输入格式

读入一个正整数 $n$。

输出格式

找出第 $n$ 个不是 squarefree 的数。

样例输入 1

10

样例输出 1

27

提示

前 $10$ 个非 squarefree 的数：$4,8,9,12,16,18,20,24,25,27$。

数据规模与约定

对于 $100 \%$ 的数据，$1\leq n \leq 10^{10}$。