Square-Free Number

Time limit2sMemory limit128 MB

Summary

Given K up to one billion, find the K-th square-free positive integer using number theory and binary search over counting functions.

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

Problem

A positive integer N is square-free if it is not divisible by any square number greater than 1. For example, 4, 9, 16, and 25 are square numbers, while 1, 2, 3, 5, 6, 7, 10, 11, 13, ... are square-free.

Given K, find the K-th square-free number in increasing order.

Input

The first line contains the integer K.

Output

Print the K-th square-free number.

Constraints

1 ≤ K ≤ 1,000,000,000

Examples4

Example 1
Input
```
13
```
Expected output
```
19
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
100
```
Expected output
```
163
```
Example 4
Input
```
1234567
```
Expected output
```
2030745
```