#include <fstream>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int mat[15][15],n,sol[15],var;
bool vizc[30],vizdp[30],vizds[30];
void bacc(int k)
{
    if(k==n)
    {
        if(var==0)
        {
            for(int i=0; i<n; i++)
                g<<sol[i]+1<<' ';
            g<<'\n';
        }
        var++;
        return;
    }
    for(int v=0; v<n; v++)
        if(!vizc[v]&&!vizdp[k-v+n]&&!vizds[k+v])
        {
            sol[k]=v;
            vizc[v]=1;
            vizdp[k-v+n]=1;
            vizds[k+v]=1;
            bacc(k+1);
            vizc[v]=0;
            vizdp[k-v+n]=0;
            vizds[k+v]=0;
        }
}

int main()
{
    f>>n;
    bacc(0);
    g<<var;
    return 0;
}