#include <fstream>

using namespace std;

ifstream be("damesah.in");
ofstream ki("damesah.out");

bool isSafe(int tabla[][100], int n, int sor, int oszlop)
{
    for(int i=0; i<sor; i++){
        for(int j=0; j<oszlop; j++){
            if(tabla[i][j]==1){
                if(abs(i-sor)==abs(j-oszlop) || j==oszlop){
                    return false;
                }
            }
        }
    }
    return true;
}

int szamlalo;
bool volt=false;

void queen(int tabla[][100], int n, int sor)
{
    if(sor==n){
        szamlalo++;
        if(!volt){
            volt=true;
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(tabla[i][j]==1){
                        ki<<j+1<<" ";
                    }
                }
            }
        }
        return;
    }

    for(int oszlop=0; oszlop<n; oszlop++){
        if(isSafe(tabla, n, sor, oszlop)){
            tabla[sor][oszlop]=1;
            queen(tabla, n, sor+1);
            tabla[sor][oszlop]=0;
        }
    }
}

int main()
{
    int n;
    be>>n;
    int tabla[100][100]={};

    queen(tabla, n, 0);
    ki<<endl<<szamlalo;

}