#include <bits/stdc++.h>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
#define int long long
const int Max = 15;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int v[Max];
bool used[Max];
int n;
int total;
bool diag(pair < int, int > p1, pair < int, int > p2)
{
    if(abs(p1.first - p2.first) == abs(p1.second - p2.second))
        return 1;
    return 0;
}
bool partial_check(int poz)
{
    pair < int, int > who;
    who = {poz,v[poz]};
    int i;
    for(i=1; i<poz; ++i)
        if(diag({i,v[i]},who))
            return 0;
    return 1;
}
bool printed;
void noted()
{
    int i;
    if(printed == 0)
    {
        printed = 1;
        for(i=1; i<=n; ++i)
            g<<v[i]<<' ';
        g<<'\n';
    }
    total ++;
}
void bkt(int k)
{
    if(!partial_check(k-1))
        return;
    if(k ==  n + 1)
    {
        noted();
        return ;
    }
    int i;
    for(i=1; i<=n; i++)
        if(used[i] == 0)
        {
            used[i] = 1;
            v[k] = i;
            bkt(k+1);
            used[i] = 0;
        }
}
void read()
{
    f>>n;
}
void solve()
{
    bkt(1);
    g<<total;
}
void restart()
{

}

int32_t main()
{
    nos();
    read();
    solve();
    restart();

    return 0;
}