#include <bits/stdc++.h>
#define VM 100
#define pb push_back

using namespace std;

int n;
int nrSol = 0;
bool ok = true;

int column[VM], line[VM];
int d1[VM], d2[VM];

vector<int> v;

void place(int i, int j, int x){
    line[i] += x;
    column[j] += x;
    d1[i - j + n] += x;
    d2[i + j] += x;
}

bool isFree(int i, int j){
    return (line[i] == 0 && column[j] == 0 && d1[i - j + n] == 0 && d2[i + j] == 0);
}

void bkt(int i){
    ///Stop
    if(i > n){
        ok = 0;
        ++nrSol;
        return;
    }
    for(int j = 1 ; j <= n ; ++j){
        if(isFree(i , j)){
            place(i , j , 1);
            if(ok)
                v.pb(j);
            bkt(i + 1);
            place(i , j , -1);
            if(ok)
                v.pop_back();
        }
    }
}


ifstream f("damesah.in");
ofstream g("damesah.out");

int main()
{
    f>>n;
    bkt(1);
    for(int i = 0 ; i < v.size() ; ++i)
        g<<v[i]<<' ';
    g<<'\n'<<nrSol;
    return 0;
}