A positive integer is said to be \textbf{squarefree }if it is not divisible by any perfect square larger than \textbf{1}. For example, the first few squarefree numbers are \{\textbf{1}, \textbf{2}, \textbf{3}, \textbf{5}, \textbf{6}, \textbf{7}, \textbf{10}, \textbf{11}, \textbf{13}, \textbf{14}, \textbf{15}, \textbf{17}, \textbf{19}, ...\}. Find the \textbf{n}-th smallest squarefree number. \InputFile The first line contains the number of tests \textbf{t}. Each of the next \textbf{t} lines contains one integer \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^9}). \OutputFile For each test case print in a separate line the \textbf{n}-th smallest squarefree number.