#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];
int rez[VM];
int size = 1;

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){
                rez[size] = j;
                ++size;
            }
            bkt(i + 1);
            place(i , j , -1);
            if(ok)
                --size;
        }
    }
}


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

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