#include<fstream>
#include<cstdlib>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N,Sol;
int X[15];

bool valid(int k)
{
    for(int i = 1 ; i < k ; ++i)
        if( X[k] == X[i] || (k-i) == abs(X[k]-X[i]) )
            return 0;
    return 1;
}

bool solutie(int k)
{
    return (k == N);
}

void afisare(int k)
{
    for(int i = 1 ; i <= N ; ++i)
        fout<<X[i]<<" ";
    fout<<"\n";
}

void Back(int k)
{
    for(int i = 1 ; i <= N ; ++i)
    {
        X[k] = i;

        if(valid(k))
        {
            if(solutie(k))
            {
                if(!Sol)  afisare(k);
                Sol++;
            }
            else    Back(k+1);
        }
    }
}

int main()
{
    fin>>N;

    Back(1);

    fout<<Sol<<"\n";

    fin.close();
    fout.close();
    return 0;
}