#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,st[101],nr;
void init(int k){
st[k]=0;
}
int succesor(int k)
{
    if(st[k]<n){
        st[k]++;
        return 1;
    }
    return 0;
}
int valid(int k)
{
    for(int i=1;i<k;i++){
        if(st[i]==st[k]) return 0;
        if(abs(k-i)==abs(st[i]-st[k])) return 0;
    }
    return 1;
}
int solutie(int k){
    return k==n;
}
void tipar(int k){
for(int i=1;i<=n;i++)
    g<<st[i]<<" ";
g<<'\n';
}
void bt(int k){
init(k);
while(succesor(k)){
    if(valid(k))
        if(solutie(k)){ if(nr>=1) nr++;
            if(nr==0){
            nr++;
            tipar(k);}}
        else{bt(k+1); }

}
}
int main()
{
  f>>n;
  bt(1);
  g<<nr;
}