#include <fstream>

using namespace std;

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

int n, v[15][15], ok = 1, cont = 0;

int verificare(int x, int y){
    for(int i = 1; i <= n; i++){
        if(v[x][i] != 0){
            return 0;
        }
    }
    for(int i = 1; i <= n; i++){
        if(v[i][y] != 0){
            return 0;
        }
    }
    int ii = x, jj = y;
    while(ii >0 && jj > 0){
        if(v[ii][jj] != 0){
            return 0;
        }
        ii--;
        jj--;
    }
    ii = x, jj = y;
    while(ii > 0 && jj <= n){
        if(v[ii][jj] != 0){
            return 0;
        }
        ii--;
        jj++;
    }
    ii = x, jj = y;
    while(ii <= n && jj > 0){
        if(v[ii][jj] != 0){
            return 0;
        }
        ii++;
        jj--;
    }
    ii = x, jj = y;
    while(ii <= n && jj <= n){
        if(v[ii][jj] != 0){
            return 0;
        }
        ii++;
        jj++;
    }
    return 1;
}

int bkt(int k, int x){
    if(k > n){
        cont++;
        if(ok){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    if(v[i][j] != 0){
                        fout<<j<<" ";
                        ok = 0;
                    }
                }
            }
        }
    }
    else{
        for(int i = 1; i <= n; i++){
            if(verificare(x, i)){
                v[x][i] = k;
                bkt(k + 1, x + 1);
                v[x][i] = 0;
            }
        }
    }
}

int main()
{
    fin>>n;
    bkt(1, 1);
    fout<<"\n"<<cont;
    return 0;
}