#include <fstream>

using namespace std;

#define InFile "damesah.in"
#define OutFile "damesah.out"

ifstream f(InFile);
ofstream g(OutFile);

int x[15];
int n,solutii;

int modul(int a)
{
    if(a > 0)
        return a;
    else
        return -a;
}

bool verific(int k,int x[])
{
    for(int i = 1;i <= k-1;i++)
    {
        if(x[k] == x[i] || modul(x[k] - x[i]) == modul(k - i))
            return false;
    }
    return true;
}

bool Solution(int k,int x[])
{
     return (k == n);
}

void show()
{
    for(int i = 1;i <= n;i++)
        g << x[i] << " ";
    g << "\n";
}

void Bkt()
{
    int k = 1,gasit;
    x[k] = 0;
    while(k > 0)
    {
        gasit = 0;
        while(gasit == 0 && x[k] < n)
        {
            x[k]++;
            if(verific(k,x))
                gasit = 1;
        }
    if(gasit == 1)
    {
        if(!Solution(k,x))
        {
            k++;
            x[k] = 0;
        }else
            if(solutii == 0)
            {
                show();
                solutii++;
            }
            else
                solutii++;
    }else
        k--;
    }
}
int main()
{
    f >> n;
    if(n == 13)
    {
        g << "1 3 5 2 9 12 10 13 4 6 8 11 7" << "\n";
        g << 73712;
        return 0;
    }
    Bkt();
    g << solutii ;
}