#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
int st[100],n,k;
ifstream f("damesah.in");
ofstream g("damesah.out");
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()
{
 f>>n;
 k=1;
 int ok=0;
 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))
        {
            if(ok<1) tipar();
            ok++;

        }
                  else
  {
       k++;
       init(k,st);
  }
       else
        k--;
 }
    g<<ok;
    f.close();
    g.close();
    return 0;

}

void init(int k, int st[])
{
    st[k]=0;
}
void succesor(int k,int st[],bool  &as)
{
    if (st[k]<n)
        {
            as=true;
            st[k]++;
        }
    else as=false;
}
void validare(int k,int st[],bool  &ev)
{
    ev=true;
    for(int i=1;i<=k-1;i++)
        {
            if(st[i]==st[k]) ev=false;
            if(abs(i-k)==abs(st[i]-st[k]))
                ev=false;
        }
}
bool solutie(int k)
{
    if(k==n) return true;
    else return false;
}
void tipar()
{
    for(int i=1;i<=k;i++)
        g<<st[i]<<" ";
    g<<endl;
}