#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N;
int SOL;
int C[20];
bool COL[20],DiagP[20],DiagS[20];
void BACKK(int k)
{
    if(k == N + 1)
    {
        if(!SOL)
            {
                for(int i = 1 ; i <= N ; ++i)
                    fout<< C[i] << ' ';
                fout<<'\n';
            }
        SOL ++;
        return;
    }
    for(int i = 1 ; i <= N ; ++i)
            if(!COL[i] && !DiagP[i-k+N] && !DiagS[i+k-1])
        {
            C[k] = i;
            COL[i] = 1;
            DiagP[i-k+N] = 1;
            DiagS[i+k-1] = 1;
            BACKK(k + 1);
            COL[i] = 0;
            DiagP[i-k+N] = 0;
            DiagS[i+k-1] = 0;
        }
   }

int main()
{
    fin >> N;
    BACKK(1);
    fout<<SOL;
    return 0;
}