Simplify the Square Root

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Tiny Wong the chef used to be a mathematics teacher in a senior high school. At that time, he always used to tell his students that when there is a square root of some number in one’s final result, it should be simplified by factoring out the largest square divisor of this number. For example, √ 12 = 2 √ 3 . Therefore, if an integer n has a square divisor, i.e. there is a number d > 1 such that d^{2} divides n, then the square root of n needs to be simplified.
Tiny himself should generate for homework some number whose square root needs simplifying. Since he used to major in Computer Science, he prefers random numbers. Therefore, he randomly chose a number n and decided to use the nth smallest number whose square root needs simplifying in today’s homework.
Since the nth such number is too large for him to deal with, Tiny Wong is lost in thought. Would you please help him?
Input
The first and only line of the input contains a single integer n.
Note: the number n is not fixed for each test case. Instead, it will be generated dynamically, so it may be different for each run of your program. For each test case, n is generated in the following way: we have two fixed numbers L and R; n will be chosen uniformly at random from all integers between L and R inclusive.
Note 2: Due to dynamically generated test cases, the problem is technically configured as interactive, thus reading until EOF will not work. Attempting to use any input method that expects EOF at the end will result in TLE verdict.
Output
Print a single line containing one integer — the nth number whose square root needs simplifying.
Constraints
 1 ≤ n ≤ 10^{18}
Subtasks
Subtask #1 (6 points): 1 ≤ n ≤ 10^{7}
Subtask #2 (17 points): 1 ≤ n ≤ 10^{14}
Subtask #3 (27 points): 1 ≤ n ≤ 10^{16}
Subtask #4 (50 points): 1 ≤ n ≤ 10^{18}
Example
Input: 4 Output: 12
Explanation
The first 4 numbers whose square roots need simplifying are 4, 8, 9 and 12.
Author:  liouzhou_101 
Editorial  https://discuss.codechef.com/problems/SQRGOOD 
Tags  dirichletconvolution, hard, jan18, liouzhou_101, numbertheory 
Date Added:  8122017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions