#include <stdio.h>
#include <math.h>
#include <limits.h>

#define MAX_N 1000001

int dp[MAX_N];

void precompute_min_moves() {
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i < MAX_N; i++) {
        // Option 1: Decrement
        dp[i] = 1 + dp[i - 1];

        // Option 2: Factorization
        // We only need to find factors up to sqrt(i)
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                int largest_factor = i / j;
                if (dp[i] > 1 + dp[largest_factor]) {
                    dp[i] = 1 + dp[largest_factor];
                }
            }
        }
    }
}

int main() {
    precompute_min_moves();

    int Q;
    scanf("%d", &Q);

    while (Q--) {
        int N;
        scanf("%d", &N);
        printf("%d\n", dp[N]);
    }

    return 0;