use std::cmp::Ordering;
use std::cmp;
use std::cmp::min;
use std::collections::BTreeMap;
use std::process;
use std::cmp::Ord;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BTreeSet;
use std::mem;
use std::collections::BinaryHeap;
use std::hash::{Hash, Hasher};

pub struct Scanner<R> {
    stdin: R,
}
 
impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        std::str::from_utf8(&buf).unwrap()
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


pub trait BinarySearch<T> {
    fn lower_bound(&self, x:&T) -> usize;
    fn upper_bound(&self, x:&T) -> usize;
}

impl<T: Ord> BinarySearch<T> for VecDeque<T>{
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}
impl<T: Ord> BinarySearch<T> for [T]{
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}
fn comb(a:usize, b:usize,  fac:&Vec<usize>, ifac:&Vec<usize>)->usize{
        let mut a = a;
        let mut b = b;
        if a == 0 && b == 0{return 1;}
        if a<b || a<0{return 0;}
        let mut tmp = ifac[a-b]*ifac[b]%MODu;
        return tmp * fac[a]%MODu;
}
fn nHr(n:usize, r:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{
    return comb(n+r-1, r, fac, ifac);
}
fn modinv(a:usize, M:usize)->usize{
    let mut b = M as i64;
    let mut u = 1 as i64;
    let mut v = 0 as i64;
    let mut a = a as i64;
    let mut m = M as i64;
    while(b>0){
        let mut t = a/b;
        a -= t*b;
        mem::swap(&mut a, &mut b);
        u-=t*v;
        mem::swap(&mut u, &mut v);
    }
    u%=m;
    if u<0{u+=m;}
    return u as usize;

}
fn modpow(x:usize, n:usize) -> usize{
        let mut ans = 1;
        let mut n = n as usize;
        let mut x = x;
        while(n != 0){
            if (n&1 == 1){ans = ans*x%MODu;}
            x = x*x%MODu;
            n = n>>1;
        }
        ans
}
fn modpow2(x:i64, n:i64, m:i32) -> i64{
        let mut ans = 1;
        let mut n = n as i64;
        let mut x = x;
        while(n != 0){
            if (n&1 == 1){ans = ans*x%m as i64;}
            x = x*x%m as i64;
            n = n>>1;
        }
        ans
}


fn invs(max:usize)->(Vec<usize>, Vec<usize>){
    let mut fac = vec![0;max+1];
    let mut ifac = vec![0;max+1];
    fac[0] = 1;
    ifac[0] = 1;
    for i in 0..max{

        fac[i+1] = fac[i] * (i+1)%MODu;
        ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu;
    }
    (fac, ifac)
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct x{    
             a:i64,   
             b:i64, 
             c:i64,   
             d:i64,   
}            
impl Ord for x{
    fn cmp(&self, other:&Self)->Ordering{
                 (other.b * (self.a)).cmp(&((self.b)*other.a))
             }        
         }            
         impl PartialOrd for x {
             fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                 Some(self.cmp(other))
             }        
         }          
fn gcd(a:usize, b:usize)->usize{
    if b==0{return a;}
    return gcd(b, a%b);
}
fn prime_factor(n:usize)->HashMap<usize, usize>{
    let mut res = HashMap::new();
    let mut n = n;
    for i in 2..n{
        if i*i>n{break;}
        while(n%i==0){
            *res.entry(i).or_insert(0)+=1;
            n/=i;
        }
    }
    if n != 1{
        res.insert(n, 1);
    }
    res
}
fn usize_multiply_is_overflow(a:usize, b:usize)->bool{
    if a<std::usize::MAX/b{
        return false;
    }
    else{
        return true;
    }
}

fn tmp(x:usize, y:usize)->usize{
    let mut ub = INFu;
    let mut lb = 1;
    while(ub-lb>1){
        let mut mid = (ub+lb)/2;
        let mut now = 1;
        let mut ok = true;
        for i in 0..y{
            if usize_multiply_is_overflow(now, mid){
                ok = false;
                break;
            }
            now*=mid;
        }
        if now>x{
            ok = false;
        }
        if ok{
            lb = mid;
        }
        else{
            ub = mid;
        }
    }
    return lb;
}
fn solve(){
    let sssss = std::io::stdin();
    let mut sc = Scanner { stdin: sssss.lock() };
    let mut test:usize =sc.read();
    for _ in 0..test{
        let mut N:usize = sc.read();
        let mut ub = INFu;
        let mut lb = 0;
        while(ub-lb>1){
            let mut mid = (ub+lb)/2;
            let mut v = vec![];
            v.push(0);
            v.push(1);

            for i in 2..65{
                v.push(tmp(mid, i)-1);
            }
            let mut t = 1;
            for i in (2..v.len()).rev(){
                let mut x = i;
                let mut now = x;
                while(now+x<v.len()){
                    v[i]-=v[now+x];
                    now+=x;
                }   
                t+=v[i];
            }
            if t>=N{
                ub = mid;
            }
            else{
                lb = mid;
            }
        }
        println!("{}", ub);
    }






}


fn main(){
    solve();
}



const PI:f64 = std::f64::consts::PI;
pub static MOD:i64    = 998244353;
pub static MODu:usize = 1000000007;
pub static MODi32:i32 = 1000000007;
pub static eps:f64 = 1e-6;
const INF: i64 = 1 << 60;
const INFu:usize = 1<<62;
const INFu128:u128 = 1<<126;