uses crt;
var a:array[1..100]of integer;
i,n,j:integer;
kt:boolean;
begin
clrscr;
readln(n);
for i:=1 to n do readln(a[i]);
for i:=1 to n do
if trunc(sqrt(a[i]))=sqrt(a[i]) then write(a[i]:4);
writeln;
for i:=1 to n do
if a[i]>1 then
begin
kt:=true;
for j:=2 to trunc(sqrt(a[i])) do
if a[i] mod j=0 then kt:=false;
if kt=true then write(a[i]:4);
end;
writeln;
readln;
end.