#include <fstream>
    #include <cmath>
    using namespace std;
    ifstream ci("checker.in");
    ofstream co("checker.out");
    int n,qu[15],way=0;
    bool ok(int a,int b)
    {
    	int i,j;
    	for(i=1;i<a;i++)
    	{
    			if(qu[i]==b || abs(i-a)==abs(qu[i]-b))
    				return 0;
    	}
    	return 1;
    }
     
    int tr(int a)
    {
    	if(a==n+1)
    	{
    		way++;
    		if(way<=3)
    		{
    			for(int i=1;i<=n-1;i++)
    				co<<qu[i]<<' ';
    			co<<qu[n]<<endl;
    		}
    		
    	}
    	else
    		for(int k=1;k<=n;k++)
    			if(ok(a,k))
    			{
    				qu[a]=k;
    				tr(a+1);
    			}
    	return 0;
    }
     
    int main()
    {
    	ci>>n;
    	tr(1);
    	co<<way<<endl;
    	ci.close();
    	co.close();
    	return 0;
    }