#include <iostream>
#include <fstream>

using namespace std;

int tabla[15][15] = {};
int megoldas[15] = {};
int db_megoldas = 0;


void Set_to_zero(int matrix[15][15], int meret)
{
    for(int i = 0; i < meret; i++){
        for(int j = 0; j < meret; j++){
            matrix[i][j] = 0;
        }
    }
}


void kiralyno_mozgas_poziciok(int meret, int tabla[15][15], int tabla_copy[15][15], int sor, int oszlop)
{
    for(int i = 0; i < meret; i++){
        for(int j = 0; j < meret; j++){
            tabla[i][j] = tabla_copy[i][j];
        }
    }
    for(int i = 0; i < meret; i++){
        tabla[sor][i] = 1;
        tabla[i][oszlop] = 1;
    }
    for(int i = 1; sor+i < meret && oszlop+i < meret; i++){
        tabla[sor+i][oszlop+i] = 1;
    }
    for(int i = 1; sor+i < meret && oszlop-i >= 0; i++){
        tabla[sor+i][oszlop-i] = 1;
    }
    for(int i = 1; sor-i >= 0 && oszlop+i < meret; i++){
        tabla[sor-i][oszlop+i] = 1;
    }
    for(int i = 1; sor-i >= 0 && oszlop-i >= 0; i++){
        tabla[sor-i][oszlop-i] = 1;
    }
}


void elhelyez(int meret, int db_kiralyno, int &db_megoldas, int tabla[15][15], int megoldas[], int sor)
{
    int tabla_copy[15][15];
    for(int i = 0; i < meret; i++){
        for(int j = 0; j < meret; j++){
            tabla_copy[i][j] = tabla[i][j];
        }
    }

    if(db_kiralyno == 0){

        db_megoldas++;
        if(db_megoldas == 1){
            for(int i = 0; i < meret; i++){
                cout << megoldas[i] << " ";
            }
        }
        Set_to_zero(tabla, meret);
        return;
    }
    bool volt_helyes_poz = false;
    for(int i = 0; i < meret; i++){
        if(tabla_copy[sor][i] == 0){
            volt_helyes_poz = true;
            kiralyno_mozgas_poziciok(meret, tabla, tabla_copy, sor, i);
            megoldas[sor] = i+1;
            elhelyez(meret, db_kiralyno-1, db_megoldas, tabla, megoldas, sor+1);
        }
    }
    if(!volt_helyes_poz){
        return;
    }

}


int main()
{
    ifstream input("damesah.in");
    ofstream output("damesah.out");
    int N;
    input >> N;

    elhelyez(N, N, db_megoldas, tabla, megoldas, 0);
    cout << endl << db_megoldas;
    return 0;
}