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

FILE *in = fopen ( "damesah.in" , "r" ) , *out = fopen ( "damesah.out" , "w" );

int i , n , solution [ 150 ] , countSolutions;
bool notGood;

void printSolution()
{
	for ( i = 1 ; i <= n ; i ++ )
		fprintf ( out , "%d " , solution [ i ] );
}

void getNextValue ( int index )
{
	notGood = true;
	if ( countSolutions == 662 && index == 5 )
        notGood = true;

	while ( notGood )
	{
		solution [ index ] ++;
		notGood = false;
		//it's on the table
		if ( solution [ index ] > n ) { solution [ index ] = 0 ; return; }

		//it's not attacking on it's line or diagonal
		for ( i = 1 ; i < index ; i ++ )
			if ( ( solution [ i ] == solution [ index ] ) || ( abs ( solution [ i ] - solution [ index ] ) == abs ( i - index ) ) )
            {
                notGood = true;
                break;
            }
	}
}

void placeQueens ( int index )
{
	while ( index > 0 )
	{
		if ( index == n + 1 ) // we have a solution
		{
			countSolutions ++;
			if ( countSolutions == 1 )
				printSolution();
            index --;
		}
		else
		{
			getNextValue ( index );
			if ( solution [ index ] == 0 )
				index --;
			else
				index ++;
		}
	}
}

int main()
{
	//read
	fscanf ( in , "%d" , &n );
	placeQueens ( 1 );
	//print the number of solutions
	fprintf ( out , "\n%d\n" , countSolutions );
	return 0;
}