#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <fstream>

using namespace std;
int st[100],n,k,q=0;

bool as,ev;
void init(int k, int st[]);
void succesor(int k,int st[],bool  &as);
void validare(int k,int st[],bool  &ev);
bool solutie(int k);
void tipar();

int main()
{int nr=0;
 ifstream f("damesah.in");
 ofstream g("damesah.out");
 f>>n;
 k=1;
 init(k,st);
 while (k>0)
 {
     do
     {
          succesor(k,st,as);
          if (as) validare(k,st,ev);
     } while (as && !ev);
  if (as)
        if (solutie(k))
       {tipar();
        nr++;}
                  else
  {
       k++;
       init(k,st);
  }
       else
        k--;
 }
g<<nr;
    return 0;
}

void init(int k, int st[])
{
   st[k]=0;
}
void succesor(int k,int st[],bool  &as)
{
 if(st[k]<n)
    {st[k]++;
     as=true;
    }
    else as=false;

}
void validare(int k,int st[],bool  &ev)
{int i;
    ev=true;
    for(i=1;i<k;i++)
        {if(st[k]==st[i]) ev=false;
         if(abs(i-k)==abs(st[k]-st[i])) ev=false;

}
}
bool solutie(int k)
{
 if(k==n) return true;
     else return false;

}
void tipar()
{int i;
    if(q==0)
    {for(i=1;i<=n;i++)
      g<<st[i]<<" ";
      g<<endl;
      q++;}
}