# include < bits/stdc++. h >

using namespace std;

int n,q,i,j;

int dp[2000000];

int flag[2000000];

int recursion(int N) {

// cout<<N<<endl;

if(N==0)
    return 0;

if(dp[N]!=-1)
    return dp[N];

int x=recursion(N-1)+1;
int y=2147483647;

for(int i=2; i*i<=N; i++)
    if(N%i==0)
        y=min(y,recursion(N/i)+1);

dp[N]=min(x,y);

return dp[N];

}

int main() {

memset(dp,-1,sizeof(dp));

scanf("%d",&q);

while(q--) {

    scanf("%d",&n);
    printf("%d\n",recursion(n));

}

return 0;

}