mod = 1000000007 eps = 10**-9 def main(): import sys from bisect import bisect_left from math import sqrt, floor input = sys.stdin.readline def square_root(n): r = floor(sqrt(n)) for x in range(3, -4, -1): if (r+x) ** 2 <= n: return r M = 15 * 10 ** 5 MAX = 2 * 10 ** 18 S = {1} for a in range(2, M+1): cur = a for b in range(2, 70): cur *= a if cur > MAX: break S.add(cur) S = sorted(list(S)) kk = bisect_left(S, M+1) for _ in range(int(input())): K = int(input()) ok = MAX ng = 0 mid = (ok + ng) // 2 while ok - ng > 1: r = square_root(mid) if r <= M: j = bisect_left(S, mid+1) if j >= K: ok = mid else: ng = mid else: k = bisect_left(S, r+1) j = bisect_left(S, mid + 1) + (r - M) - (k - kk) if j >= k: ok = mid else: ng = mid mid = (ok + ng) // 2 print(ok) assert ok != MAX if __name__ == '__main__': main()