{*******************************************}
{* Program Name: dfs3                      *}
{* Input File: dfs3.in                     *}
{* Output File: dfs3.out                   *}
{* Date:2008.7.19                          *}
{* Programmer:PengBo                       *}
{*******************************************}
Program dfs3;
type
  sz=array[1..50]of byte;
  bl=array[1..50]of boolean;
var
  s:sz;
  f:bl;
  n:byte;
  g:int64;
  o:text;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
function zs(x:byte):boolean;
var
  i:byte;
  t:boolean;
begin
  t:=true;
  if odd(x)
  then
  begin
    for i:=3 to trunc(sqrt(x)) do
      if (x mod i =0)
      then
      begin
        t:=false;
        break;
      end
  end
  else
    t:=false;
  zs:=t;
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure cs;
var
  i:byte;
begin
  g:=0;
  for i:=1 to n do
  begin
    s[i]:=i;
    f[i]:=false;
  end;
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure input;
var
  i:text;
begin
  assign(i,'dfs3.in');
  reset(i);
  read(i,n);
  close(i);
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure outputf;
begin
  assign(o,'dfs3.out');
  rewrite(o);
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure outputs;
var
  i:byte;
begin
  for i:=1 to n do
    write(o,s[i],' ');
  writeln(o);
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure main(m:byte);
var
  i:byte;
  v:boolean;
begin
  if m<=n
  then
  begin
    for i:=1 to n do
    begin
      if not(f[i])
      then
      begin
        s[m]:=i;
        f[i]:=true;
        main(m+1);
        f[i]:=false;
      end;
    end;
  end
  else
  begin
    v:=true;
    for i:=1 to (n-1) do
      if zs(s[i]+s[i+1])=false
      then
      begin
        v:=false;
        break;
      end;
    if v
    then
    begin
      outputs;
      inc(g);
    end;
  end;
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
begin
  input;
  cs;
  outputf;
  main(1);
  write(o,g);
  close(o);
end.