Square-Free Number

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