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

int N,Sol;
int X[15];
bool Col[15],Diag_p[30],Diag_s[30];

bool valid(int l,int c)
{
    if(Col[c])  return 0;
    if(Diag_p[l-c+N])   return 0;
    if(Diag_s[l+c-1])   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,i))
        {
            Col[i] = Diag_p[k-i+N] = Diag_s[k+i-1] = 1;

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

            Col[i] = Diag_p[k-i+N] = Diag_s[k+i-1] = 0;
        }
    }
}

int main()
{
    fin>>N;

    Back(1);

    fout<<Sol<<"\n";

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