program ex;
type
 zs=array[1..10]of integer;
 ss=array[1..20000,0..1]of integer;
 sz=array[1..20000]of boolean;
var
 a:zs;
 f:ss;
 g:sz;
 n,maxn:integer;
procedure init;
 var
  i,j:integer;
 begin
  assign(input,'stonegame.in');
  assign(output,'stonegame.out');
  reset(input);
  rewrite(output);
  readln(n);
  maxn:=0;
  for i:=1 to n do
   begin
    readln(a[i]);
    if a[i]>maxn then maxn:=a[i];
   end;
  close(input);
  for i:=2 to maxn do g[i]:=true;
  for i:=2 to maxn do
   for j:=2 to trunc(sqrt(i)) do
    if (i mod j=0) then
     begin
      g[i]:=false;
      break;
     end;
 end;
procedure main;
 var
  i,j:integer;
  min1,min2:integer;
  flag:boolean;
 begin
  for i:=2 to maxn do
   begin
    min1:=maxint;
    min2:=maxint;
    flag:=false;
    if (g[i])or(g[i-1]) then
             begin
              f[i,1]:=1;
              f[i,0]:=1;
             end
             else
              begin
               for j:=i downto 2 do
                if g[j] then
                 begin
                  if f[i-j,0]=-1 then
                   if f[i-j,1]<min1 then min1:=f[i-j,1];
                  if f[i-j,0]=1 then
                   if f[i-j,1]<min2 then min2:=f[i-j,1];
                 end;
               if min1=maxint then
                              begin
                               f[i,0]:=-1;
                               f[i,1]:=min2+1;
                              end
                             else begin
                                   f[i,0]:=1;
                                   f[i,1]:=min1+1;
                                  end;
              end;
   end;
  for i:=1 to n do
   begin
    if f[a[i],0]=1 then writeln(f[a[i],1])
                   else writeln(-1);
   end;
 end;
begin
 init;
 main;
 close(output);
end.