#include <iostream>
#include <fstream>
#define MAX 13

using namespace std;
int n, dame[MAX], coloane[MAX], diagonale_left[4 * MAX - 2], diagonale_right[4 * MAX - 2], first = 1, contor;
ifstream in("damesah.in");
ofstream out("damesah.out");
void afisare()
{
  int i;

  for(i = 0; i < n; i++)out << dame[i] + 1 << " ";
  out << endl;
}
bool validare(int k)
{
  if(coloane[dame[k]] == 1)return 0;
  if(diagonale_left[n - k + dame[k] - 1] == 1 || diagonale_right[2 * n - k - dame[k] - 2] == 1)return 0;
  return 1;
}
void bkt(int k)
{
  int i;

  for(i = 0; i < n; i++)
  {
    dame[k] = i;
    if(validare(k))
    {
      coloane[i] = 1;
      diagonale_left[n - k + i - 1] = diagonale_right[2 * n - k - i - 2] = 1;
      if(k + 1 == n)
      {
        if(first == 1)
        {
          afisare();
          first = 0;
        }
        contor++;
        coloane[i] = 0;
        diagonale_left[n - k + i - 1] = diagonale_right[2 * n - k - i - 2] = 0;
      }
      else bkt(k + 1);
      coloane[i] = 0;
      diagonale_left[n - k + i - 1] = diagonale_right[2 * n - k - i - 2] = 0;
    }
  }
}
int main()
{
  in >> n;
  bkt(0);
  out << contor;
  in.close();
  out.close();
  return 0;
}