#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

int nr;
int sol;
const int NMAX = 14;
int st[NMAX];
int n;


ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
void backtrack(int k);
void printSol();
int isOk(int k);

int main()
{

    nr = 0;
    sol = 0;

    fin >> n;
    backtrack(1);
    fout << nr << '\n';

    return 0;

}

void backtrack (int k)
{
    for(int i=1; i<=n ;i++)
    {
        st[k] = i;
        if(isOk(k))
        {
            if(k == n)
            {
                nr++;
                if(sol == 0)
                {
                    printSol();
                    sol = 1;
                }
            }
            else
                backtrack(k+1);

        }

    }

}


int isOk(int k)
{
   int j;
   for(j=1; j<k; j++)
   {
       if(st[k] == st[j])
        return 0;
        if(abs(st[j] - st[k]) ==  abs(j - k))
        return 0;

   }

   return 1;

}

void printSol()
{

    for(int i=1; i<=n; i++)
    fout << st[i] << " ";
    fout << '\n';

}