program xmz;
var
 f1,f2:text;
 f,sm,bg,z,x:array[0..20000]of longint;
 c:array[0..20000]of boolean;
 a,b,n,max,d,zn:longint;
 procedure zhi;
  begin
   for a:=2 to max do
     if not c[a] then
      begin
       inc(zn);
       z[zn]:=a;
       b:=a+a;
       while b<=max do
        begin
         c[b]:=true;
         b:=b+a;
        end;
      end;
  end;
 begin
 assign(f1,'stonegame.in');assign(f2,'stonegame.out');
 reset(f1);rewrite(f2);
 read(f1,n);
 for a:=1 to n do
  begin
  read(f1,x[a]);
  if max<x[a] then max:=x[a];
  end;
 zhi;
 f[0]:=-1;f[1]:=-1;
 for a:=2 to max do
  begin
  sm[a]:=100000000;
  b:=1;
  while (z[b]<=a)and(b<=zn) do
  begin

   if (f[a-z[b]]=-1)and(sm[a]>bg[a-z[b]]+1) then sm[a]:=bg[a-z[b]]+1;
   if (f[a-z[b]]<>-1)and(bg[a]<sm[a-z[b]]+1) then bg[a]:=sm[a-z[b]]+1;
   if f[a-z[b]]=-1 then d:=1;
   b:=b+1;
  end;
  if d<>1 then f[a]:=-1;
  d:=0;
  end;

  for a:=1 to n do
   if f[x[a]]=0 then writeln(f2,sm[x[a]]) else writeln(f2,-1);
 close(f1);close(f2);
end.