#include<fstream>
#include<cstring>
using namespace std;
bool c[31],i[41],r[31];
int n,ans,temp[15];
void dfs(int x) 
{
    for(int y=1;y<=n;y++)
        if (c[y+13] && i[y+x+13] &&r[y-x+13])
        {
            temp[x]=y;
            c[y+13]=false;
            i[y+x+13]=false;
            r[y-x+13]=false;
            if(x<n)
                dfs(x+1);
            else
            {
                if(ans<3)
                {
                    for (int i=1;i<=n;i++)
                        printf("%d ",temp[i]); 
                    printf("\n"); 

                }
                ans++;
                if (ans>14244)
                {
                    ans+=59467;
                    return;
                }
            }
            c[y+13]=true;
            i[y+x+13]=true;
            r[y-x+13]=true;
        }
}
int main()

{
    freopen("checker.in","r",stdin);
    freopen("checker.out","w",stdout);
    scanf("%d",&n);
    memset(c,true,sizeof(c));
    memset(i,true,sizeof(i));
    memset(r,true,sizeof(r));
    ans=0;
    dfs(1);
    printf("%d",ans);
   return 0;
}