#include using namespace std; typedef long long int ll; typedef pair P; typedef vector VI; typedef vector VVI; #define REP(i,n) for(ll i=0;i<(n);i++) #define ALL(v) v.begin(),v.end() template bool chmax(T &x, const T &y) {return (x bool chmin(T &x, const T &y) {return (x>y)?(x=y,true):false;}; constexpr ll MOD=998244353; constexpr ll INF=2e18; const double eps=1e-8; map mp; ll p(ll x, ll y){ ll res=1; REP(i,y) res*=x; return res; } ll f(ll x){ if(x<=1) return 0; if(mp[x]!=0) return mp[x]; ll res=x-1; for(int i=2;i<=60;i++){ double r=pow(x,(double)1/i)+eps; ll rr=r; //if(p(rr,i)>x) rr--; res-=f(rr); } return mp[x]=res; } int main(){ int t; cin >> t; while(t--){ ll k; cin >> k; ll l=0, r=INF; while(r-l>1){ ll m=(l+r)/2; if(m-f(m)