using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static int[] NList => ReadLine().Split().Select(int.Parse).ToArray(); static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray(); public static void Main() { Solve(); } static void Solve() { var t = NN; var ans = new long[t]; for (var u = 0; u < t; ++u) { var k = NN; var ok = 1_000_000_000_000_000_001L; var ng = 0L; while (ok - ng > 1) { var mid = (ok + ng) / 2; var count = 0L; foreach (var j in primes) { var iok = 1L; var ing = max[j] + 1; while (ing - iok > 1) { var imid = (iok + ing) / 2; if (IsOverN(imid, j, mid)) ing = imid; else iok = imid; } count += iok - 1; } ++count; if (count >= k) ok = mid; else ng = mid; } ans[u] = ok; } WriteLine(string.Join("\n", ans)); } static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59 }; static long[] max = new long[] { 0, 0, 1_000_000_000, 1_000_000, 31622, 3981, 1000, 372, 177, 100, 63, 43, 31, 24, 19, 15, 13, 11, 10, 8, 7, 7, 6, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }; static bool IsOverN(long i, int j, long n) { var prev = 1L; var ij = 1L; for (var x = 0; x < j; ++x) { ij *= i; if (prev >= ij || ij % i != 0) return true; prev = ij; } return ij > n; } }