program dfs3(f1,f2);
var
  a:array[1..51] of integer;
  i,j,n,k,t,l,x:integer;
  f1,f2:text;
  f:boolean;
procedure try1(i,l:integer);
begin
  x:=2; f:=true;
  while f and (l<trunc(sqrt(i+l)+1)) do begin
    if (i+l) mod x=0 then f:= false;
    inc(l);
  end;
end;
procedure try(i:integer);
begin
  a[j+1]:=i;
  if j<n then begin
      while i<=n do begin
        try1(i,a[j]);
        if f then begin
            j:=j+1; i:=1; try(i);
          end
          else i:=i+1;
       end;
    end
    else begin
      t:=t+1;
      for k:=1 to n do write(f2,a[k],' ');
      writeln(f2);
    end;
end;
begin
  assign(f1,'dfs3.in'); assign(f2,'dfs3.out');
  reset(f1); rewrite(f2);
  read(f1,n); j:=1; t:=0;
  for i:=1 to n do begin
    a[1]:=i; try(i);
  end;
  write(f2,t);
  close(f1);  close(f2);
end.