#include <bits/stdc++.h>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int st[40] , viz[40] , n , ok;
void Print(int top)
{
    int i;
    ///daca indicele este egal cu elementul din stiva => regina!!!
    /// * -> regina
    if(ok == 1)
    {
        for(i = 1; i <= top; i++)///parcurg indicii
            fout << st[i] << " ";
        fout << "\n";
    }
}
int Check(int top , int x)
{
    int i;
    ///doua regine se afla pe aceeasi diagonala daca abs(i - top) == abs(x - st[i]);
    if(top == 1)return 1;
    for(i = 1; i < top; i++)
        if(abs(i - top) == abs(x - st[i]))return 0;
    return 1;
}
void Back(int top)
{
    int i;
    if(top == n + 1)
        {
            ok++;
            Print(n);
        }
    else for(i = 1; i <= n; i++)
        if(viz[i] == 0 && Check(top , i) == 1)
        {
            st[top] = i;
            viz[i] = 1;
            Back(top + 1);
            viz[i] = 0;
        }
}
int main()
{
    fin >> n;
    Back(1);
    fout << ok << "\n";
    return 0;
}