#include <fstream>

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

struct asd{
    int col,diag1,diag2;
}fol[20];
int total,n;
int st[40];

void afisare(){
    if(total == 0){
        for(int i = 1; i <= n; i++){
            g << st[i] <<" ";
        }
        g <<"\n";
    }
    total++;
}
void back(int k){
    for(int i = 1; i <= n; i++){
        if(fol[i].col == 0 && fol[k - i + n - 1].diag1 == 0 && fol[k + i].diag2 == 0){
            fol[i].col = 1;
            fol[k - i + n - 1].diag1 = 1;
            fol[k + i].diag2 = 1;

            st[k] = i;

            if(k == n)
                afisare();
            else
                back(k + 1);

            fol[i].col = 0;
            fol[k - i + n - 1].diag1 = 0;
            fol[k + i].diag2 = 0;
        }
    }
}
int main()
{
    f >> n;
    back(1);
    g << total;
    return 0;
}