Square-Free Number

Time limit

Memory limit

128 MB

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