#include <bits/stdc++.h>

using namespace std;

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

int n, st[14], k;

int valid(int p)
{
    for(int i=1; i<p; i++)
        if(st[i]==st[p] || abs(st[i]-st[p])==abs(i-p))
        return 0;
    return 1;
}
int solutie(int p)
{
    return p==n;
}
void tipar(int p)
{
    for(int i=1; i<=p; i++)
        fout<<st[i]<<" ";
    fout<<'\n';
}
void bk(int p)
{
    for(int i=1; i<=n; i++)
    {
        st[p]=i;
        if(valid(p))
            if(solutie(p))
            {
                k++;
                if(k==1)
                    tipar(p);
            }
            else
                bk(p+1);
    }
}
int main()
{
    fin>>n;
    bk(1);
    fout<<k<<'\n';
    return 0;
}