#include <fstream>
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

long long n, cnt;
int a[20][20];

void printsol() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 1)
                fout << j << " ";
        }
    }
    fout << '\n';
}

bool verif(int l, int c) {
    // Check if placing a queen at (l, c) is safe:

    // Check if there is a queen in the same row or column
    for (int i = 1; i <= n; i++) {
        if (a[l][i] == 1 || a[i][c] == 1)
            return false;
    }

    // Check diagonals (top-left to bottom-right and top-right to bottom-left)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i - j == l - c || i + j == l + c) {
                if (a[i][j] == 1)
                    return false;
            }
        }
    }

    return true;
}

void asezD(int c) {
    if (c > n) {
        cnt++;
        if (cnt == 1) {
            printsol();
        }
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (verif(i, c)) {
            a[i][c] = 1;
            asezD(c + 1);
            a[i][c] = 0;
        }
    }
}

int main() {
    fin >> n;
    asezD(1);
    fout << cnt;
    return 0;
}