#include <iostream>
#include <math.h>
#include<fstream>
#include <stdlib.h>

using namespace std;
int N, Count, k;
bool ok, print = true;
int x[13];

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

void printSol()
{
    for(int i = 0; i < N; i++)
        g << x[i] << " ";
    g << "\n";
}
void backTraking()
{
    while(k >= 0){
           ok = false;
           while((x[k] < N-1) && (!ok)){
               ok = true;
               x[k]++;
               for(int i = 0; (i < k) && ok; i++){
                   if ((x[k] == x[i]) || (k - i == abs(x[k] - x[i])))
                    ok = false;
               }
           }
           if(!ok) k--;
           else{
               if(k == N-1){
                   Count++;
                   if(print) {printSol(); print = false;}
               }
               else {
                   k++;
                   x[k] = -1;
               }
           }
       }
}

int main()
{
    f >> N;
    backTraking();
    g << Count << "\n";
}