#include <assert.h>
#include <stdio.h>

#define MAX_N 14

FILE *f;
int n, numSol;
unsigned sol[MAX_N];      // vectorul soluție
// bitset de ocupare a coloanelor și diagonalelor
// dacă bitul x din col este 1, atunci coloana x este liberă
// dacă bitul x din diag este 1, atunci diagonala c - l + n - 1 = x este liberă
// dacă bitul x din anti este 1, atunci antidiagonala l + c = x este liberă
unsigned col, anti, diag;   

// Calculează logaritmul în baza 2. Presupune că x este putere a lui 2.
int log(unsigned x) {
  int r = 0;
  while (x > 1) {
    x >>= 1;
    r++;
  }
  return r;
}

void backtrack(int l) {
  if (l == n) {
    if (++numSol <= 3) {
      for (int i = 0; i < n; i++) {
        fprintf(f, "%d ", 1 + log(sol[i]));
      }
      fprintf(f, "\n");
    }
  } else {
    // Shiftăm și facem AND pe cele trei măști pentru a obține masca pătratelor
    // de pe linia l pe care putem amplasa o damă. Aceasta este cheia optimizărilor,
    // căci pe linia l efortul nu va mai fi O(n), ci maxim O(n - 1 - l).
    unsigned mask = col & (anti >> l) & (diag >> (n - 1 - l));

    // Iterăm doar prin biții setați
    while (mask) {
      unsigned lsb = mask & (-(signed)mask); // lsb este 1 << indexul_coloanei_libere
      sol[l] = lsb;
      col ^= lsb;
      anti ^= lsb << l;
      diag ^= lsb << (n - 1 - l);
      backtrack(l + 1);
      col ^= lsb;
      anti ^= lsb << l;
      diag ^= lsb << (n - 1 - l);
      mask ^= lsb;
    }
  }
}

int main(void) {
  f = fopen("regine.in", "r");
  assert(fscanf(f, "%d", &n) == 1);
  fclose(f);

  f = fopen("regine.out", "w");

  // Reducem la jumătate timpul: amplasăm prima regină doar în jumătatea stângă
  // a primei linii, apoi înmulțim numărul de rezultate cu 2. Caz special
  // pentru table de dimensiune impară, unde coloana de la jumătate nu trebuie
  // înmulțită cu 2
  for (int c = 0; c < (n + 1) / 2; c++) {
    sol[0] = 1 << c;
    col = ((1 << n) - 1) ^ (1 << c);
    anti = ((1 << (2 * n - 1)) - 1) ^ (1 << c);
    diag = ((1 << (2 * n - 1)) - 1) ^ (1 << (n - 1 + c));
    backtrack(1);
    if (c == n / 2 - 1) {
      numSol *= 2;
    }
  }

  // Metoda de mai sus nu se descurcă bine pentru n = 6, căci există doar
  // două soluții în jumătatea stângă. O tipărim explicit pe a treia.
  // Există și metode mai curate, dar sunt prea complexe.
  if (n == 6) {
    fprintf(f, "4 1 5 2 6 3 \n");
  }

  fprintf(f, "%d\n", numSol);
  fclose(f);
}