#include<fstream>
#include<cstdlib>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int k,q,s[100],n,i,qq=1,nrsol;
int verificare(int x)
{
    q=1;
    for(i=1; i<x && q; i++)
    {
        if(s[x]==s[i]) q=0;
        if(abs(s[x]-s[i])==abs(x-i))
            q=0;
    }
    return q;
}
void afisare()
{
    if(qq==1)
    {
    for(i=1;i<=k;i++)
        g<<s[i]<<" ";
    g<<'\n';
    nrsol++,qq=0;
    }
    else
        nrsol++;
}
int main()
{
    f>>n;
    k=1;
    s[k]=0;
    while(k>0)
    {
        q=0;
        while(q==0&&s[k]+1<=n)
        {
            s[k]++;
            q=verificare(k);
        }
    if(q)
        if(k==n)
            afisare();
        else
            k++,s[k]=0;
    else
        k--;
    }
    g<<nrsol;
}