program n116；
var ans:array[0..10000]of longint；
nzz:array[0..30000]of boolean；
f,g,from,orz:array[0..30000]of longint；
n,i,m,j,my:longint；
begin
readln(n)；
m:=0；
for i:=1 to n do
begin
readln(ans[i])；
if ans[i]>m then m:=ans[i]；
end；
nzz[1]:=true；
for i:=2 to trunc(sqrt(m)) do
for j:=2 to m div i do nzz[i*j]:=true；
j:=0；
for i:=2 to m do
begin
if not nzz[i] then
begin
inc(j)；
orz[j]:=i；
from[i]:=j；
end
else
from[i]:=j；
end；
f[1]:=-1；g[1]:=0；
for i:=2 to m do
begin
if (not nzz[i]) or (not nzz[i-1]) then
begin
f[i]:=1；
continue；
end；
my:=123456789；
for j:=1 to from[i] do if (f[i-orz[j]]=-1) and (my>g[i-orz[j]]) then my:=g[i-orz[j]]；
if my<>123456789 then f[i]:=my+1
else
begin
f[i]:=-1；
my:=-2；
for j:=1 to from[i] do
if (f[i-orz[j]]<>-1) and (my<f[i-orz[j]]) then my:=f[i-orz[j]]；
g[i]:=my+1；
end；
end；
for i:=1 to n do writeln(f[ans[i]])；
end.