//na                            :cuixiaofei;
//da                            :08_09_19;
program dfs3;
  var
    n,ge                        :longint;
    zhishu,ji,a                 :array[1..1000] of longint;
    f1,f2                       :text;
  procedure init;
  begin
    assign(f1,'dfs3.in');
    reset(f1);
    assign(f2,'dfs3.out');
    rewrite(f2);
    ge:=0;
    readln(f1,n);
    fillchar(ji,sizeof(ji),0);
  end;
  procedure zhaozhishu;
    var
      i,j                       :longint;
  begin
    for i:=1 to 1000 do
      zhishu[i]:=1;
    zhishu[1]:=0;
    for i:=2 to 1000 do
      if zhishu[i]=1 then
        begin
          for j:=i to 1000 div i do
            begin
              zhishu[i*j]:=0;
            end;
        end;
  end;

  procedure sousuo(k:longint);
    var
      i                         :longint;
  begin
    if k=n+1 then
      begin
        for i:=1 to n do
          write(f2,a[i],' ');
        writeln(f2);
        inc(ge);
      end
    else if k=1 then
      begin
        for i:=1 to n do
          if ji[i]=0 then
          begin
            ji[i]:=1;
            a[k]:=i;
            sousuo(k+1);
            ji[i]:=0;
          end;
      end
    else
      begin
        if a[k-1] mod 2 =0 then
          i:=1
        else
          i:=2;
            while i<=n do
              begin
                if (ji[i]=0) and (zhishu[i+a[k-1]]=1) then
                  begin
                    ji[i]:=1;
                    a[k]:=i;
                    sousuo(k+1);
                    ji[i]:=0;
                  end;
                i:=i+2;
              end;
      end;
  end;

  procedure main;
  begin
    zhaozhishu;
    sousuo(1);
  end;
  procedure print;
  begin
    writeln(f2,ge);
    close(f1);
    close(f2);
  end;
  begin
    init;
    main;
    print;
  end.