function pal(var n,osn: integer): boolean;
var a: array[1..32] of integer;
    i,k,m,p: integer;
begin
  k:=1; m:=n;
  p:=0;
  while m>0 do
  begin
    p:=p+1;
    a[p]:=(m mod osn);
    m:=m div osn;
  end;
  for i:=1 to p div 2 do
  if a[i]<>a[p-i+1] then k:=0;
  pal:=(k>0);
end;

// основная программа
const mx=10;
var m,i,j,tm: integer;
    b: array[1..mx] of integer;
    priz: boolean; 
begin
  readln(m);
  for i:=1 to m do readln(b[i]);
  for i:=1 to m do
  begin
    priz:=true;
    if b[i]<4 then priz:=false;
    for j:=2 to ceil(sqrt(b[i])) do
      if pal(b[i],j) then priz:=false;
    if priz then writeln('YES')
    else writeln('NO'); 
  end;
end.