#include <fstream>
#include <cmath>
using namespace std;
ifstream fi("damesah.in");
ofstream fo("damesah.out");
int n;
int backtrack(int n)
{
    int k,sol,nrsol=0,i,A[15],pos,prima=1;
    k=1;
    A[1]=0;
    while(k!=0)
    {
        sol=0;
        while(sol!=1 && A[k]<n)
        {
            A[k]++;
            pos=1;
            for(i=1;i<k;i++)
                if(A[k]==A[i] || abs(A[k]-A[i])==k-i)
                {
                    pos=0;
                    break;
                }
            if(pos==1)
                sol=1;
        }
        if(sol==0)
            k--;
        else
        {
            if(k==n)
            {
                if(prima)
                {
                    for(i=1;i<=n;i++)
                        fo<<A[i]<<" ";
                    fo<<'\n';
                    prima=0;
                }
                nrsol++;
            }
            else
            {
                k++;
                A[k]=0;
            }
        }
    }
    return nrsol;
}
int main()
{
    fi>>n;
    fo<<backtrack(n);
    fi.close();
    fo.close();
    return 0;
}