include

using namespace std;

const int MAXN = 1000000; int dp[MAXN+1];

int main() { ios::sync_with_stdio(false); cin.tie(NULL);

dp[0] = 0;
for(int i=1; i<=MAXN; i++) {
    dp[i] = dp[i-1] + 1;
    for(int j=2; j*j <= i; j++) {
        if(i % j == 0) {
            int a = j;
            int b = i / j;
            dp[i] = min(dp[i], dp[max(a,b)] + 1);
        }
    }
}

int Q; cin >> Q;
while(Q--) {
    int N; cin >> N;
    cout << dp[N] << "\n";
}
return 0;

}