#include<bits/stdc++.h>
using namespace std;

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

int n, sol = 0, S[15];
bool col[15], d1[32], d2[32];
bool afisat = false;

void cit()
{
    fin>>n;
}

void afiseaza()
{
    for(int i = 1; i <= n; i++)
    {
        fout<<S[i];
        if(i < n)
            fout<<' ';
    }
    fout<<"\n";
}

bool valid(int x, int y)
{
    if(col[y] == true || d1[x-y+n] == true || d2[x+y-1] == true )
        return false;
    return true;
}

inline void fix(int x, int y)
{
    col[y] = d1[x-y+n] = d2[x+y-1] = 1;
    S[x] = y;
}

inline void revin(int x, int y)
{
    col[y] = d1[x-y+n] = d2[x+y-1] = 0;
    S[x] = 0;
}

void bk(int index)
{
    if(index == n+1)
    {
        sol++;
        if(!afisat)
        {
            afiseaza();
            afisat = true;
        }
    }
    else
    {
        for(int j = 1; j <= n; j++)
            if(valid(index, j))
            {
                fix(index, j);
                bk(index + 1);
                revin(index, j);
            }
    }
}

int main()
{
    cit();
    bk(1);
    fout<<sol;
    return 0;
}