check

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
//#define int ll
//#define double ld
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int , int>
#define pb emplace_back
#define endl '\n'
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define F first
#define S second
const int mod = 1e9 + 7;
const int MAXX = 1e7 + 5;
const int OP = 1e3 + 5;
const int N = 1e3;
const int INF = 1e18 + 123;

int t  , n , k;
int dp[MAXX];
bool p[OP];
vector<int> v;

void sieve(){
    p[2] = true;
    for(int i = 3; i <= N; i += 2){
        p[i] = true;
    }
    for(int i = 3; (i * i) <= N; i += 2){
        if(p[i]){
            for(int j = (i + i + i); j <= N; j += (i + i)){
                p[j] = false;
            }
        }
    }
    v.pb(2);
    for(int i = 3; i <= N; i += 2){
        if(p[i])
            v.pb(i);
    }
}

int main()
{
    _FastIO;
    sieve();
    v.pb(1001);
    dp[1] = 0;
    dp[2] = 1;
    int m = 1;
    for(int i = 3; i <= 1e6; i++){
        dp[i] = i - m;
        k = i;
        for(int j = 0; (v[j] * v[j]) <= i; j++){
            if(i % v[j])
                continue;
            while(k % v[j] == 0){
                k /= v[j];
            }
            dp[i] = min(dp[i] , dp[i / v[j]] + v[j]);
        }
        if(k > 1){
            dp[i] = min(dp[i] , dp[i / k] + k);
        }
        m = max(m , i - dp[i]);
    }


    scanf("%d" , &t);
    while(t--){
        scanf("%d" , &n);
        printf("%d" , dp[n]);
        putchar('\n');
    }
    return 0;
}