#include<bits/stdc++.h>

using namespace std;
    ifstream f("damesah.in");
    ofstream g("damesah.out");
int n, nr_sol;
int viz[15], v[15];

bool check(int k)
{
    for(int i = 1 ; i < k ; i++){
        if(abs(v[k] - v[i]) == k - i){
            return false;
        }
    }
    return true;
}

void afisare()
{
    for(int i = 1 ; i<= n ; i++){
        g<<v[i]<< " ";
    }
    g<<'\n';
}

void backtr(int k,int len)
{
     if(k-1 == len)
     {
        if(!nr_sol){
            afisare();
        }
        nr_sol++;
     }
     else
     {
         for(int  i = 1; i <= len; i++)
            if(!viz[i])
           {
                 v[k] = i;
                 viz[i] = 1;
                 if(check(k)){
                    backtr(k+1,len);
                 }
                 viz[i] = 0;
           }
     }
}

int main()
{
    f>>n;
    backtr(1, n);
    g<<nr_sol;
}