#include <iostream>
#include <fstream>

using namespace std;

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

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


void print(int board[10][10]){
    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[10][10], 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;
        }
    }
    return true;
}

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

    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 true;
}

bool check(){
    int board[10][10];
    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;
}