#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");

int sah[15][15], nr, ok, n, vp[25], vs[25], vc[15];
vector <int> coloana;

bool verif(int l, int c)
{
    if(vc[c]==1 || vp[l-c+n]!=0 || vs[l+c-1]!=0)
        return false;
    return true;
}
void backtracking(int l)
{
    for(int i=1;i<=n;i++)
    {
        if(verif(l, i))
        {
            vc[i]=1;
            vp[l-i+n]++;
            vs[l+i-1]++;
            coloana.push_back(i);
            if(l==n)
            {
                if(nr==0){
                    for(unsigned int j=0;j<coloana.size();j++)
                        g<<coloana[j]<<' ';
                    g<<'\n';
                }
                nr++;
            }
            else
                backtracking(l+1);
            coloana.pop_back();
            vc[i]=0;
            vp[l-i+n]--;
            vs[l+i-1]--;
        }
    }
}
int main()
{
    f>>n;
    backtracking(1);
    g<<nr;
    return 0;
}