program dfs3;
var
  n,n2,i,j,k,p:longint;
  sz:array[0..50,0..50]of integer;
  answer,hx:array[1..50]of integer;
procedure find(c:integer);
var
  i:integer;
begin
  if c>n then begin
    for k:=1 to n-1 do
    begin
      write(answer[k],' ');
    end;
    write(answer[n]);
    writeln;
    n2:=n2+1;
  end
  else begin
    for i:=1 to sz[c-1,0] do
    begin
      if hx[sz[c-1,i]]=0 then begin
        hx[sz[c-1,i]]:=1;
        answer[c]:=sz[c-1,i];
        find(c+1);
        hx[sz[c-1,i]]:=0;
      end;
    end;
  end;
end;
begin
  assign(input,'dfs3.in');
  assign(output,'dfs3.out');
  reset(input);
  rewrite(output);
  readln(n);
  fillchar(sz,sizeof(sz),0);
  fillchar(hx,sizeof(hx),0);
  sz[0,0]:=n;
  for i:=1 to n do
    sz[0,i]:=i;
  for i:=1 to n do
    for j:=1 to n do
    begin
      if i<>j then begin
        p:=0;
        for k:=2 to i+j-1 do
          if (i+j)mod k=0 then begin
            p:=1;
            break;
          end;
        if p=0 then begin
          sz[i,0]:=sz[i,0]+1;
          sz[i,sz[i,0]]:=j;
        end;
      end;
    end;
  n2:=0;
  find(1);
  writeln(n2);
  close(input);
  close(output);
end.