include

include

include

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;[](https://)