#include <iostream>
#include <fstream>

using namespace std;

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

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

int abs(int a){
    if(a < 0){
        return -a;
    }
    else{
        return a;
    }
}


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


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

//    for(int i = row, j = col; i >= 1 && j >= 1; i--, j--){
//        if(board[i][j] != 0){
//            return false;
//        }
//    }
//
//    for(int i = row, j = col; i >= 1 && j <= n; i--, j++){
//        if(board[i][j] != 0){
//            return false;
//        }
//    }

    for(int i = 1; i < row; i++){
        for(int j = 1; j <= n; j++){
            if((board[i][j] == 1) && (abs(j - col) == abs(i - row))){
                return false;
            }
        }
    }

    return true;
}

void solveQueen(int board[13][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] = 1;
            solveQueen(board, row + 1);

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

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

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


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

    return 0;
}