#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("damesah.in");
ofstream g ("damesah.out");

int n,pos,dpl[20];
bool atc[20],atd[100];
void dame(int linie){
  if(linie<n){
    for(int i=1;i<=n;i++){
      if(not atc[i]&&not atd[linie+i]&&not atd[linie-i+100]){
        atc[i]=atd[linie+i]=atd[linie-i+100]=true;
        dpl[linie]=i;
        dame(linie+1);
        atc[i]=atd[linie+i]=atd[linie-i+100]=false;
      }
    }
  } else {
    int i;
    for(i=1;atc[i];i++);
    if(not atd[linie+i]&&not atd[linie-i+100]){
      pos++;
      dpl[linie]=i;
      if(pos==1){
        for(int ii=1;ii<=n;ii++)
          g<<dpl[ii]<<" ";
        g<<'\n';
      }
    }
  }
}

int main()
{
    f>>n;
    dame(1);
    g<<pos;
    f.close ();
    g.close ();
    return 0;
}