Non-Squarefree Numbers

Time limit2sMemory limit32 MB

Summary

Given n up to 10^10, find the n-th positive integer that is divisible by some square d^2 with d > 1.

Level: Hard8 of 10
Topics: Binary search, Math, Number theory, Combinatorics
Solved: No attempts yet

Problem

A positive integer $k$ is called squarefree if it is not divisible by $d^2$ for any integer $d > 1$ . Conversely, $k$ is called non-squarefree if there exists an integer $d > 1$ such that $d^2$ divides $k$ .

For example, listing the non-squarefree numbers in increasing order gives $4, 8, 9, 12, 16, \dots$ .

Print the $n$ -th non-squarefree number when they are listed in increasing order.

Input

The first line contains an integer $n$ ( $1 \le n \le 10^{10}$ ).

Output

Print the $n$ -th non-squarefree number on a single line.

Examples1

Example 1
Input
```
10
```
Expected output
```
27
```