Kth Squarefree Number

Little X has always loved numbers. However, he has an unusual dislike: he despises all perfect squares other than \(1\). In fact, he finds these numbers so displeasing that he even dislikes any positive integer that is a multiple of any perfect square (other than \(1\)). Thus, he loves only those numbers which are squarefree (i.e. numbers that are not divisible by any perfect square greater than \(1\)).

On his birthday, little W wants to gift him a number. Naturally, he cannot gift little X a number that little X hates. So, little W lists all the numbers that little X does not hate and selects the \(K\)th number from that list. Little X happily accepts the gift.

Your task is to help little W remember which number he gifted by finding the \(K\)th squarefree number.

inputFormat

The input contains a single integer \(K\) \( (1 \leq K \leq 10^5)\), representing the position (1-indexed) in the list of squarefree numbers.

outputFormat

Output the \(K\)th squarefree number.

sample

1

1