import java.util.*;
import java.util.ArrayList;
public class Main {
    public static void main(String args[]) {
        int  x=new Scanner(System.in).nextInt();
         while(x!=0){
            long s=new Scanner(System.in).nextLong();
             long p=0,d=0;
             while(s!=1)
             { d=0;
                 for(int i=2;i*i<=s;i++)
                 {
                     if(s%i==0)
                     {
                         s=i;
                         p++;
                         d=1;
                         break;
                     }
                 }
                 if(d==0)
                { s--;
                 p++;}
             }
            x--;
            System.out.println(p);
         }
    }
}