The Perfect Gift

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

It is the season of giving and NK is making a gift for his idol, Zeyu.

Zeyu likes most natural numbers (\(1, 2, 3, 4, ..\)), but not all natural numbers. Specifically, Zeyu doesn't like square numbers. So, NK decided to write a list of all the natural numbers that Zeyu likes (all natural numbers except for square numbers).

Unfortunately, NK is practicing for the CCC, so he asks you to help him out a bit. NK wants to know what the \(Q\)-th element of his list is.


\(1 \le Q \le 10^9\)

Subtask 1 [30%]

\(1 \le Q \le 10^5\)

Input Specification

The first and only line contains an integer \(Q\), which is the index of the element you want to find.

Output Specification

Output the \(Q\)-th element of his list.

Sample Input


Sample Output



NK's list starts with \([2, 3, 5, 6, 7]\). Therefore, the fifth element of his list is \(7\).


There are no comments at the moment.