#include <bits/stdc++.h>
using namespace std;

int n,a[100],NrSol;
void putfunc(int);
ofstream damesah("damesah.out");
int main() {
ifstream dame("damesah.in");
    dame>>n;
putfunc(0);
damesah<<'\n';
damesah<<NrSol;
return 0;
}

void solution()
{
    int i,j;
    ++NrSol;
    if (NrSol==1) for (i=0;i<n;i++)
        {for (j=0;j<n;j++)
        if (j==a[i]) damesah<<j+1<<' ';}
}
void putfunc(int k)
{
    int i,j,check;
    if (k==n) solution();
    else for (i=0;i<n;i++)
    {
        for (check=1,j=0;j<k;j++)
            if (a[j]==i || abs(a[j]-i)==(k-j)) check=0;
        if (check) {a[k]=i;putfunc(k+1);}
    }
}