#include <fstream>
#define MAX 30
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n,nr,col[MAX],diag1[MAX],diag2[MAX],queen[MAX];//1- principala, 2- secundara
bool used;

void bkt(int x);
void print();

int main(){
    fin>>n;
    bkt(1);
    fout<<nr;
    return 0;
}
void bkt(int row){
    if(row>n){
        if(!used)
            print(),
            used=1;
        ++nr;
        return;
    }
    for(int i=1;i<=n;++i){
        if(!col[i] && !diag1[n+i-row] && !diag2[i+row]){
           col[i]=diag1[n+i-row]=diag2[i+row]=true;
           queen[row]=i;

           bkt(row+1);

           col[i]=diag1[n+i-row]=diag2[i+row]=false;
        }
    }
}
void print(){
    int i;
    for(i=1;i<=n;++i)
        fout<<queen[i]<<' ';
    fout<<'\n';
}