#include <fstream>

std::ifstream input ("damesah.in");
std::ofstream output ("damesah.out");

int solutionCount = 0;
bool firstsolutionFound = false;

void solve(int size, int currentRow, int arr[]) {

    //col = column
    //arr[row] = queenColumn
    if (currentRow < size) {
        for (int col = 1; col <= size; col++) {
            bool canPlace = true;
            for(int prevRow = 1; prevRow < currentRow; prevRow++) {
                if (arr[prevRow] == col || abs(currentRow - prevRow) == abs(col - arr[prevRow])) {
                    canPlace = false;
                    break;
                }
            }
            if (canPlace) {
                arr[currentRow] = col;
                solve(size, currentRow + 1, arr);
            }
        }
    }

    else {
        for (int col = 1; col <= size; col++) {
            bool canPlace = true;
            for(int prevRow = 1; prevRow < currentRow; prevRow++) {
                if (arr[prevRow] == col || abs(currentRow - prevRow) == abs(col - arr[prevRow])) {
                    canPlace = false;
                    break;
                }
            }
            if (canPlace) {
                arr[currentRow] = col;
                solutionCount++;
                if (!firstsolutionFound) {
                    firstsolutionFound = true;
                    for (int i = 1; i <= size; i++) {
                        output << arr[i] << " ";
                    }
                    output << "\n";
                }
            }
        }
    }
}

int main () {

    int n;
    input >> n;
    if (n == 1){
        output << 1 << "\n" << 1;
        return 0;
    }
    int arr[n+1];
    solve(n, 1, arr);
    output << solutionCount;

    return 0;
}