#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int k=0;
int gasit=1;
void backtr(int poz,vector<int> p,int n,vector<int> folosit)
{
    if(poz==n+1)
    {
        int i,j;
        int ok=1;
        for(i=0;i<p.size();i++)
        for(j=1+i;j<p.size();j++)
        {
            if(abs(i-p[i])==abs(j-p[j]))
            ok=0;
        }
        if(ok==1)
        {
            if(gasit==1)
            {
                for(i=0;i<p.size();i++)
                g<<p[i]<<" ";
                g<<endl;
            }
            
        
            gasit++;
            k++;
            
        }
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(folosit[i]==0)
        {
            p.push_back(i);
            folosit[i]=1;
            
            backtr(poz+1,p,n,folosit);
            p.pop_back();
            folosit[i]=0;
        }
    }
    
}
int main()
{
    int n;
    //cout<<"Dati n ";
    f>>n;
    
    vector<int> p;
    vector<int> folosit(n+1,0);
    
    backtr(1,p,n,folosit);
    g<<k;
    
    return 0;
}