#include <stdlib.h>
#include <fstream>

using namespace std;

ifstream f("damesah.in");
ofstream f2("damesah.out");

int n, c = 0;
bool executed = true;

void print(int board[13]){
    for(int i = 1; i <= n; i++){
        f2 << board[i] << " ";
    }
}


bool isValid(int board[13], int row, int col){
    for(int i = 1; i < row; i++){
        if(board[i] == col){
            return false;
        }
        if((abs(board[i] - col) == abs(i - row))){
            return false;
        }
    }

    return true;
}

void solveQueen(int board[13], int row){
    if(row > n){
        c++;
        if(executed == true){
            print(board);
            executed = false;
        }
        return;
    }

    for(int i = 1; i <= n; i++){
        if(isValid(board, row, i) == true){
            board[row] = i;
            solveQueen(board, row + 1);

            board[row] = 0;
        }
    }
    return;
}

bool check(){
    int board[13];
    for(int i = 1; i <= n; i++){
        board[i] = 0;
    }
    solveQueen(board, 1);

    f2 << endl;
    f2 << c;
    return true;
}


int main()
{
    f >> n;
    check();

    return 0;
}