Натуральне число називається \textbf{вільним від квадратів}, якщо воно не ділиться на жодний квадрат числа, більший за \textbf{1}. Наприклад, першими числами, вільними від квадратів, будуть \{\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}, ...\}. Знайдіть \textbf{n}-те найменше вільне від квадратів число. \InputFile Перший рядок містить кількість тестів \textbf{t}. Кожен з наступних \textbf{t} рядків містить одне натуральне число \textbf{n} (\textbf{1 }≤ \textbf{n} ≤ \textbf{10^9}). \OutputFile Для кожного тесту вивести в окремому рядку \textbf{n}-те найменше число, вільне від квадратів.