#include <fstream>

using namespace std;

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

int n, sol[14], nr;
bool gasit = true;

bool ok (int pozitie)
{
  int i, j, ii, jj, p;
    for (i=1; i<pozitie; i++)
    {
        if (sol[i] == sol[pozitie])
            return false;
        if (abs(i - pozitie) == abs(sol[i] - sol[pozitie]))
            return false;
    }
  return true;
}

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

void bkt (int k)
{
    for (int i=1; i<=n; i++)
    {
        sol[k] = i;
         if (ok(k))
         {
             if (k == n)
             {
                if (gasit)
                {
                    afisare();
                    gasit = false;
                }
                nr ++;
             }
             else
                bkt(k+1);
         }
    }
}

int main()
{
  f >> n;
  bkt(1);
  g  << nr;
    return 0;
}