#include <bits/stdc++.h>

using namespace std;

int N;

bool isFirst = true;
vector< pair<int,int> > rs;

bool isAvailable(pair<int,int> queen, const vector< pair<int,int> > &queens) {
    //cout << queen.first << " " << queen.second << endl;
    for (auto prev_queen: queens) {
        if (prev_queen.second == queen.second) return false;
        if ( abs(prev_queen.second - queen.second) == abs(prev_queen.first - queen.first) ) return false;
    }

    return true;
}

int backtrack(int row, int N,  vector< pair<int,int> > &queens) {
    if (row > N) {
        //cout<< "got here" << endl;
        if (isFirst) {
            rs = queens;
            isFirst = false;
        }
        return 1;
    }
    int sum = 0;
    for (int column = 1; column <= N; column++) {
        if (isAvailable(make_pair(row, column), queens)) {
            queens.push_back({row, column});
            sum += backtrack(row + 1, N, queens);
            queens.pop_back();
        }
    }
    return sum;
}

int just_cheating[] = { 0,0,0,0, 
                        2,
                        10,
                        4,
                        40,
                        92,
                        352,
                        724,
                        2680,
                        14200,
                        73712
};

int main() {
    ifstream cin("damesah.in");
    ofstream cout("damesah.out");

    cin >> N;
    vector< pair<int,int> > queens;
    int cnt =  backtrack(1, N, queens);
    for (auto it: rs) cout << it.second << " ";
    cout << endl;
    cout << cnt;

    //cout << just_cheating[N];
    // for (int i = 4; i <= 13; i++) {
    //     vector< pair<int,int> > emptyVec;
    //     cout << backtrack(1, i, emptyVec) << endl;
    // }
    


    return 0;
}