#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
using namespace std;
bool d[100]={0},b[100]={0},c[100]={0};
int sum=0,a[100];
	int n;
int search(int);
int print();

int main(){

	cin>>n;
	search(1);
	
	cout<<sum;
	return 0;
}


int search(int i){
	while(i<=n){
	
		int j;
        for(j=1;j<=n;j++)
        if(!b[j]&&(!c[i+j])&&(!d[i-j+n]))
        {
            a[i]=j;
            b[j]=1;
            c[i+j]=1;
            d[i-j+n]=1;
             sum++;
             if(sum<4)print();
             search(i+1);
            b[j]=0;
            c[i+j]=0;
            d[i-j+n]=0;
           
            
        }
    }
}

    int print(){
       
       	for(int k=1;k<=n;k++)
            cout<<a[k]<<" ";
            cout<<endl;
        
		
	}```cpp