program stonegame;
type
fxz=array[0..20000] of longint;
var
  i,nc,t,n:longint;
  s,b,c,f:fxz;
procedure calc;
var
  flag:array [2..20000] of boolean;
  i,j:longint;
begin fillchar (flag,sizeof(flag),true);
      for i:=2 to 20000 do if flag[i] then 
   begin
      inc(nc);c[nc]:=i;j:=2*i;
      while j<=20000 do begin flag[j]:=false;
                              j:=j+i;
                          end;
    end;
end;
procedure get(p:integer);
var i:integer;
begin
  f[p]:=0;s[p]:=100000000;
  for i:=1 to nc do if c[i]>p then break else begin
    if f[p-c[i]]=-1 then get(p-c[i]);
    if f[p-c[i]]=0 then begin
      f[p]:=1;
      if b[p-c[i]]+1<s[p] then s[p]:=b[p-c[i]]+1;
    end
    else if s[p-c[i]]+1>b[p] then b[p]:=s[p-c[i]]+1;
  end;
end;
begin
  nc:=0;calc;
  fillchar (f,sizeof(f),$FF);
  fillchar (s,sizeof(s),0);
  fillchar (b,sizeof(b),0);
  assign (input,'stonegame.in');
  reset (input);
  assign (output,'stonegame.out');
  rewrite (output);
  readln (n);
  for i:=1 to n do begin
    readln (t);
    get(t);
    if f[t]=0 then writeln (-1) else writeln (s[t]);
  end;
  close (output);
  close (input);
end.