#include <iostream>
#include <vector>


using namespace std;

class NQueensProblem{
public:
    NQueensProblem(int n = 8);
    void printTable();
    void removeQueen(int row, int col);
    void setQueen(int row, int col);
    void setImpactOnPosition(int row, int col, int option);
    void setImpactOnRow(int row, int col, int option);
    void setImpactOnColumn(int row, int col, int option);
    void setImpactOnDiagonal(int rol, int col, int option);
    void setImpactOnAntiDiagonal(int rol, int col, int option);
    void setImpactOnTable(int row, int col, int option);
    int findNextAvailablePositionInColumn(int row, int col);
    int printAllSolutions();
public:
    void initTable();
    int* rowOfQueenAtColumn;
    int** table;
    int N;
    int solutionsCounter;
};

void NQueensProblem::initTable(){
    table = new int*[N];
    rowOfQueenAtColumn = new int[N];
    for ( int i = 0 ; i < N ; i ++ ){
		table[i] = new int[N];
        for ( int j = 0 ; j < N ; j ++ ){
            table[i][j] = 0;
        }
        rowOfQueenAtColumn[i] = -1;
    }
}

NQueensProblem::NQueensProblem( int n ){
    N = n;
    solutionsCounter = 0;
    initTable();
}

void NQueensProblem::printTable() {
    for ( int i = 0 ; i < N ; i ++ ){
        for ( int j = 0 ; j < N ;  j ++ ){
            if ( table[i][j] > 1 ){
            cout<<"# ";
            }
            else {
                cout<<"Q ";
            }
        }
        cout<<endl;
    }
    cout<<endl;
}

void NQueensProblem::removeQueen(int row, int col) {
    setImpactOnTable(row, col, -1);
}

void NQueensProblem::setQueen(int row, int col) {
    setImpactOnTable(row,col,1);
}

void NQueensProblem::setImpactOnPosition(int row, int col, int option) {
    table[row][col] += option;
}

void NQueensProblem::setImpactOnRow(int row, int col, int option) {
    for ( int j = 0 ; j < N ; j ++ ){
        if ( j == col ) {
        continue;
        }
        table[row][j] += option;
    }
}

void NQueensProblem::setImpactOnColumn(int row, int col, int option) {
    for ( int i = 0 ; i < N ; i ++ ) {
        if ( row == i ) {
        continue;
        }
        table[i][col] += option;
    }
}

void NQueensProblem::setImpactOnDiagonal(int row, int col, int option) {
    int i = row - 1;
    int j = col - 1;
    while ( i >= 0 && j>= 0 ) {
        table[i][j] += option;
        i--;
        j--;
    }
    i = row + 1;
    j = col + 1;
    while ( i < N && j < N ){
        table[i][j] += option;
        i++;
        j++;
    }
}

void NQueensProblem::setImpactOnAntiDiagonal(int row, int col, int option) {
    int i = row - 1;
    int j = col + 1;
    while ( i >= 0 && j < N ) {
        table[i][j] += option;
        i--;
        j++;
    }
    i = row + 1;
    j = col - 1;
    while ( i < N && j >= 0 ) {
        table[i][j] += option;
        i++;
        j--;
    }
}

void NQueensProblem::setImpactOnTable(int row, int col, int option ) {
    setImpactOnPosition(row, col, option);
    setImpactOnRow(row, col, option);
    setImpactOnColumn(row, col, option);
    setImpactOnDiagonal(row, col, option );
    setImpactOnAntiDiagonal(row, col, option);
}

int NQueensProblem::findNextAvailablePositionInColumn(int row, int col) {
    int i = row + 1;
	if ( row == -1 ){
		while ( i < N && table[i][col] != 0 ) {
			i++;
		}
	}
	else {
		while ( i < N && table[i][col] > 1 ) {
			i++;
		}
	}
    if ( i == N ) {
    return -1;
    }
    return i;
}

int NQueensProblem::printAllSolutions() {
    setQueen(0,0);
    rowOfQueenAtColumn[0] = 0;
    int col = 1;
    while ( col >= 0 ) {
        int row = findNextAvailablePositionInColumn(rowOfQueenAtColumn[col], col);
        if ( row != -1 ) {
			if ( rowOfQueenAtColumn[col] != -1 ){
				removeQueen(rowOfQueenAtColumn[col],col);
			}
            setQueen(row, col);
            rowOfQueenAtColumn[col] = row;
            col++;
            if ( col == N ) {
                printTable();
                solutionsCounter++;
                col--;
            }
        }
        else {
            if ( rowOfQueenAtColumn[col] != -1 ) {
                removeQueen(rowOfQueenAtColumn[col],col);
                rowOfQueenAtColumn[col] = -1;
            }
            col--;
        }

    }
    return solutionsCounter;
}


int main () {
    int n;
    cin>>n;
    NQueensProblem queens(n);
    queens.printAllSolutions();
	cout<<queens.solutionsCounter<<endl;

    return 0;

}

