#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

int cnt;

const int MAX = 2169800;
const int INF = 1000000000;

struct segment{
    int val;
    int lazy;
    int koji;
} seg[4*MAX+5];

int sta[MAX+5];

void propagate(int node, int l, int r){
    seg[node].val += seg[node].lazy;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    seg[node*2].lazy += seg[node].lazy;
    seg[node*2+1].lazy += seg[node].lazy;
    seg[node].lazy = 0;
}

void updatuj(int node, int l, int r){
    seg[node].val = min(seg[node*2].val+seg[node*2].lazy, seg[node*2+1].val+seg[node*2+1].lazy);
    if(seg[node*2].val+seg[node*2].lazy == seg[node].val) seg[node].koji = seg[node*2].koji;
    else seg[node].koji = seg[node*2+1].koji;
}

void updseg(int node, int l, int r, int tl, int tr, int val){
    if(l > tr || tl > r) return;
    if(tl <= l && r <= tr){
        seg[node].lazy += val;
        propagate(node, l, r);
        return;
    }
    propagate(node, l, r);
    int mid = (l+r)/2;
    updseg(node*2, l, mid, tl, tr, val);
    updseg(node*2+1, mid+1, r, tl, tr, val);
    updatuj(node, l, r);
}

void updpoint(int node, int l, int r, int x, int val){
    if(l == r){
        seg[node].koji = l;
        seg[node].val = val;
        seg[node].lazy = 0;
        return;
    }
    propagate(node, l, r);
    int mid = (l+r)/2;
    if(mid >= x) updpoint(node*2, l, mid, x, val);
    else updpoint(node*2+1, mid+1, r, x, val);
    updatuj(node, l, r);
}

void init(int node, int l, int r){
    if(l == r){
        seg[node].koji = seg[node].val = INF;
        return;
    }
    seg[node].koji = seg[node].val = INF;
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
}

int getval(int node, int l, int r, int x){
    propagate(node, l, r);
    if(l == r) return seg[node].val;
    int mid = (l+r)/2;
    if(mid >= x) return getval(node*2, l, mid, x);
    return getval(node*2+1, mid+1, r, x);
}

/// MOJE
void solve(){
    int n;
    cin >> n;
    /*if(n < sta[cnt]){
        int l = 1;
        int r = cnt;
        while(l < r){
            int mid = (l + r) / 2;
            if(sta[mid] > n)r = mid;
            else l = mid+1;
        }
        cout << l << endl;
        return;
    }*/
    if(n == 1){
        cout << 1 << endl;
        return;
    }
    if(n == 2){
        cout << 2 << endl;
        return;
    }
    int res = 0;
    int vel = n-1;
    res = 1;
    for(int i=1; i<=cnt; i++){
        if(vel == 0)break;
        res++;
        int broj = sta[i];
        int pomvel = (vel + broj - 1) / broj;
        vel -= pomvel;
        if(i == cnt){
            cout << sta[i] << " " << pomvel << " " << vel+pomvel << endl;
        }
        if(pomvel == 1){
            break;
        }
    }
    res += vel;
    cout << res << endl;
}


int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);

    int n;
    n = 418*1e5;
    init(1, 1, MAX);
    /// ne zaboravi da dodas 1, 2, 3 u niz
    sta[++cnt] = 2;
    sta[++cnt] = 3;
    int kurac = 2;
    for(int i=5; i<=n; i+=6-kurac){
        updseg(1, 1, MAX, 1, cnt, -1);
        if(seg[1].val+seg[1].lazy){
            sta[++cnt] = i;
            updpoint(1, 1, MAX, cnt, sta[cnt]);
        }
        else{
            int k = seg[1].koji;
            updseg(1, 1, MAX, k+1, cnt, 1);
            updpoint(1, 1, MAX, k, sta[k]);
        }
        kurac = 6-kurac;
    }
    //cout << cnt+3 << endl;
    int t;
    cin >> t;
    while(t--)solve();
    return 0;
}