#include <fstream>
#include <cmath>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, sol,a[1000];
void wr()
{
    for(int i=1;i<=n;i++)
        g<<a[i]<<' ';
    g<<'\n';
}
bool bate(int x, int y, int k)
{
    bool t=true;
  for(int j=k;j>0&&t;j--)
  {
      if(a[j]==y || abs(j-x)==abs(a[j]-y)) t=false;
  }
  return t;
}
void dame(int k)
{
    if(k==n) {sol++; if(sol==1)wr();}
    else
    {
       for(int i=1;i<=n;i++)
       {
         if(bate(k+1,i,k))
         {a[k+1]=i; dame(k+1); a[k+1]=0;}
       }
    }
}
int main()
{
   f>>n;

  dame(0);

  g<<sol;

    return 0;
}