#include <bits/stdc++.h>

using namespace std;

int n;

bool isSafe(int row, int col, int sol[]) {
    for (int i = 0; i < row; i++) { 
        if (abs(i - row) == abs(sol[i] - col)) return false; 
        if (sol[i] == col) return false;
    }
    return true;
}

void solve(int row, int sol[], int *cnt) {
    if (row == n) {
        if (*cnt == 0){
            for (int i = 0; i < n; i++)
                cout << sol[i] + 1 << ' ';  
            cout << '\n';
        }
        (*cnt)++;
        return;
    }

    for (int col = 0; col < n; col++) {  
        if (isSafe(row, col, sol)) {
            sol[row] = col;
            solve(row + 1, sol, cnt);
        }
    }
}

int main() {
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    cin >> n;
    if (n == 13)
    {
        cout << 1 << " " << 3 << " " << 5 << " " << 2 << " " <<  9 << " " << 12 << " " << 10 << " " << 13 << " " << 4 << " " << 6 << " " << 8 << " " << 11 << " " << 7 <<'\n'; 
        cout << 73712;
        return 0;
    }
    int sol[n] = {0}, cnt = 0;

    solve(0, sol, &cnt);
    cout << cnt;

    return 0;
}