#include <fstream>
#include <cmath>
using namespace std;

int st[100];
int n, s=0;
bool af=false;

ifstream f("damesah.in");
ofstream g("damesah.out");

bool succesor(int k)
{
    if(st[k]<n)
    {
    st[k]++;
    return 1;
    }
    return 0;
}

bool valid(int k)
{
    bool ev=true;
    for(int i=1; i<k; i++)
        if(st[i]==st[k] || abs(st[k]-st[i])==k-i)
        ev=false;
    return ev;
}

void back(int k)
{
    if(k==n+1)
    {
    if(!af){
    for(int i=1; i<=n; i++)
        g<<st[i]<<" ";
        g<<'\n';
        af=true;
    }
    s++;
    }
    else
    {
    st[k]=0;
    while(succesor(k))
        if(valid(k))
        back(k+1);
    }
}

int main()
{
    f>>n;
    back(1);
    g<<s;
    return 0;
}