#include <bits/stdc++.h>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
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;
    printed = 1;
    for(i=1; i<=n; ++i)
        g<<v[i]<<' ';
    g<<'\n';
}
void bkt(int k)
{
    if(!partial_check(k-1))
        return;
    if(k ==  n + 1)
    {
        if(printed == 0)
        {
            printed = 1;
            noted();
        }
        total ++;
        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()
{
    if(n!=13)
    {
        bkt(1);
        g<<total;
    }
    else
    {
        g<<"1 3 5 2 9 12 10 13 4 6 8 11 7 "<<'\n';
        g<<"73712";
    }

}
void restart()
{

}

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

    return 0;
}