import sys from math import sqrt input = sys.stdin.readline def f(N): cnt = [0] * 60 for i in range(59, 1, -1): ok = 0 ng = int((10**18 + 100000)**(1/i)) while ng - ok > 1: mid = (ok + ng) // 2 if mid ** i <= N: ok = mid else: ng = mid ok -= 1 cnt[i] = ok - sum(cnt[::i]) return sum(cnt) + 1 # print(f(10)) def main(): K = int(input()) ok, ng = 10**18, 0 while ok - ng > 1: mid = (ok + ng) // 2 if f(mid) >= K: ok = mid else: ng = mid print(ok) if __name__ == '__main__': T = int(input()) for _ in range(T): main()