program Smith;

var
i,N:integer;
a:array[1..10] of integer;

function s1(a:integer):integer;
var
x,s:integer;
begin
s:=0;
while a<>0 do begin
x:=a mod 10;
s:=s+x;
a:=a-x;
a:=a div 10;
end;
s1:=s;
end;

function s2(a:integer):integer;
var
x,s,h:integer;         t:boolean;
begin
if a=1 then s2:=0;
t:=true;            h:=2;
while t AND (h<=a) do begin
if a mod h =0 then begin
t:=false;
s2:=s2(a div h)+s1(h);
end
else h:=h+1;
end;
end;

function proc(a:integer):boolean;
var
x:integer;
begin
x:=2;
proc:=false;
for x:=2 to trunc(sqrt(a)) do
if a mod x=0 then proc:=true;
end;

function sm(a:integer):boolean;
begin
if (s1(a)=s2(a)) AND (proc(a)) then sm:=true
else sm:=false;
end;

begin
read(N);
for i:=1 to N do
read(a[i]);
for i:=1 to N do
while NOT(sm(a[i])) do a[i]:=a[i]+1;
for i:=1 to N do
write(a[i],' ');
end.

