记录编号	2580	评测结果	AAAAAA
题目名称	[HAOI 2004模拟]数列问题	最终得分	100
用户昵称	WaterFire	是否通过	通过
代码语言	Pascal	运行时间	0.999 s
提交时间	2008-09-22 22:09:51	内存使用	0.13 MiB

program waterfire;
const
fin='dfs3.in';
fout='dfs3.out';
var
s,i,j,n,max:longint;
a:array[1..15] of longint;
b:boolean;
data:array[1..15,1..1000] of boolean;
f,g:text;
k:array[1..15] of boolean;



procedure judge(x:longint);
var
i,j:longint;
begin
b:=true;
for i:=2 to trunc(sqrt(x)) do
if x mod i=0 then b:=false;
end;

procedure print(c,d:longint);
var
ii,jj,cc:longint;
begin{main}
if s=n+1 then
   begin
    for cc:=1 to n-1 do
    write(g,a[cc],' ');
    writeln(g,a[n]);
    inc(max);
    exit;
   end;
for ii:=1 to n do
 if (data[d,ii]=true)and(k[ii]=true) then
  begin
  k[ii]:=false;
  a[s]:=ii;
  inc(s);

  print(d,ii);
  dec(s);
  k[ii]:=true;
  end;
 end;{main}


begin
assign(f,fin);reset(f);
assign(g,fout);rewrite(g);
s:=3;
read(f,n);
for i:=1 to n-1 do
 for j:=i+1 to n do begin
  judge(i+j);
  if b=true then
  begin
  data[i,j]:=true;
  data[j,i]:=true;
  end;
  end;
  for i:=1 to n do
   for j:=1 to n do
  if data[i,j]=true then
  begin
  if (i mod 2=0)and(n mod 2<>0) then continue;
  a[1]:=i;a[2]:=j;
  fillchar(k,sizeof(k),true);
  k[i]:=false;k[j]:=false;
  print(i,j);
  end;
  writeln(g,max);
  close(f);
  close(g);
end.