#include <bits/stdc++.h>
using namespace std;

ofstream fout("damesah.out");
ifstream fin("damesah.in");

int x[50],k,valid,n,m,nr;
bool u=true;

void citire(){
     //cout<<"n=";
	 fin>>n;
}

void posibil(int k,int &valid){
     valid=1;
     for(int i=1;i<=k-1;i++) if(abs(x[i]-x[k])==abs(i-k)||(x[i]==x[k])) valid=0; 
}

int solutie(int k){
     if(k==n) return 1;
        else return 0;}

/*void afisare(int k){
     nr++;
     cout<<"solutia "<<nr<<endl;
     for(int i=1;i<=k;i++){
      for (int j=1;j<=k;j++)
        if (x[i]==j) cout<<"0"<<" ";
            else cout<<"1"<<" ";
		cout<<endl;}
}*/

void afisare(int k){
     nr++;
     if(u==true){
     for(int i=1;i<=k;i++)
      for (int j=1;j<=k;j++)
        if (x[i]==j) fout<<j<<' ';
		u=false;}
}

void back(){
    k=1;
    x[k]=0;
    while(k>0){
        valid=0;
		while(!valid && x[k]<n){
		x[k]=x[k]+1;
		posibil(k,valid);}
		if(!valid) k--;
				else if(solutie(k)) afisare(k);
				     else {
				           k++;
						   x[k]=0;}}
}

int main(){
   citire();
   nr=0;
   back();
   fout<<endl<<nr;
   return 0;
}