#include<fstream>
#include<cmath>
using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
int a[15],n,nr;
void afisare (int l)
{
  for( int i=1;i<=l;i++)
     fout<<a[i]<<" ";
}
bool verifica ( int l)
 {
   for( int j=1;j<l;j++)
   {

     int b= fabs(a[j]-a[l]);
        if(b==l-j || a[j]==a[l])
         return false;

   }
   return true;
 }
void dame(int n,int k)
{
  if(k==n+1)
     return;
  else
     for( int i=1;i<=n;i++)
     {
       a[k]=i;
       if(verifica(k) )
         {
           if(k==n  && !nr)
            {
              afisare(k);
              nr++;
            }
            else if(k==n)
              nr++;
          dame(n,k+1);
        }
     }
}
int main()
{
  fin>>n;
  nr=0;
  dame(n,1);
  fout<<"\n";
  fout<<nr;

}