Const Fi='BEAUTY.INP';
      Fo='BEAUTY.OUT';
Var f,g: text;
    i,n,d,s: longint;
    A: array[1..1000] of longint;
Function ngto(a: longint): boolean;
Var i: longint;
Begin
        If a<2 then exit(false);
        For i:=2 to a div 2 do
                If a mod i = 0 then exit(false);
        exit(true);
End;

Function bpcs(b: longint): longint;
Var s: longint;
Begin
        s:=0;
        While b<>0 do
        Begin
                s:=s+sqr(b mod 10);
                b:=b div 10;
        End;
        bpcs:=s;
End;


Begin
        Assign(f,Fi); Reset(f);
        Assign(g,Fo); Rewrite(g);
        n:=0;

        While not eof(f) do
        Begin
                inc(n);
                Readln(f,A[n]);
        End;

        For i:=1 to n do
        Begin
                d:=0; s:=10;
                While d<A[i] do
                Begin
                        If ngto(bpcs(s)) then inc(d);
                        inc(s);
                End;
                Writeln(g,s-1);
        End;

        Close(f);
        Close(g);
End.

const fi='sodep.inp';
      fo='sodep.out';
var a: array [0..100000] of longint;
    i,dem:longint;
function checkprime(x:longint):boolean;
var dem:byte;
    c:longint;
begin
        if x<=1 then exit(false);
        for c:=2 to trunc(sqrt(x)) do if x mod c = 0 then exit(false);
        exit(true);
end;
function check(x:longint):boolean;
begin
        if checkprime((x mod 10)*(x mod 10)+(x div 10)*(x div 10)) then exit(true);
        exit(false);
end;
begin
        assign(input,fi);
        reset(input);
        while not eof() do
                begin
                        readln(a[dem]);
                        inc(dem);
                end;
        close(input);
        assign(output,fo);
        rewrite(output);
        for i:=0 to dem do
                if check(a[i]) then writeln(a[i]);
        close(output);
end.