program dfs3;
  var
    a:array[1..50]of boolean;
    b:array[1..50]of integer;
    s:array[1..100]of boolean;
    n:integer;
    e:longint;
    f1,f2:text;
    procedure init;
      var
        i:integer;
      begin
        assign(f1,'dfs3.in');reset(f1);
        assign(f2,'dfs3.out');rewrite(f2);
        read(f1,n);
        close(f1);
        for i:=1 to n do a[i]:=true;
      end;
    procedure jian;
      var
        i,j,k:integer;
        f:boolean;
      begin
        s[2]:=true;
        for i:=1 to 97 do begin
          f:=true;
          j:=2;
          while f and (j<trunc(sqrt(i))+1) do begin
            if i mod j =0 then f:=false;
            inc(j);
          end;
          s[i]:=f;
        end;
      end;
    procedure try(i:integer);
      var
        j,k:integer;
      begin
        for j:=1 to n do begin
          if a[j] and((i=1)or(s[j+b[i-1]])) then begin
            b[i]:=j;
            a[j]:=false;
            if i=n then begin
              inc(e);
              for k:=1 to n do write(f2,b[k],' ');
              writeln(f2);
            end
            else try(i+1);
            a[j]:=true;
            b[i]:=0;
          end;
        end;
      end;
  begin
    init;
    e:=0;
    fillchar(b,sizeof(b),0);
    fillchar(s,sizeof(s),false);
    jian;
    try(1);
    write(f2,e);
    close(f2);
  end.