#include <bits/stdc++.h>
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n,nrsol=0;
void afis(int sol[],int nr){
  for(int i=1;i<nr;i++){
    fout<<sol[i]<<' ';
  }
  fout<<'\n';
}
bool cond(int sol[],int nr,int i){
  for(int j=1;j<nr;j++)
  {
    if(sol[j]-j==i-nr)
    return 0;
    if(sol[j]+j==i+nr)
    return 0;
  }
  return 1;
}
void bkt(int nr,int sol[],int fr[]){
  if(nr>n){
    nrsol++;
    if(nrsol==1){
      afis(sol,nr);
    }
  }else{
    for(int i=1;i<=n;i++)
    {
      if(fr[i]==0 && cond(sol,nr,i)){
        sol[nr]=i;
        fr[i]=1;
        bkt(nr+1,sol,fr);
        fr[i]=0;
      }
    }
  }
}

int main(int argc, char const *argv[]) {
  fin>>n;
  int sol[n+1],fr[n+1]={0};
  bkt(1,sol,fr);
  fout<<nrsol;
  return 0;
}