#include <bits/stdc++.h>
using namespace std;
int n,ans;
int s[17];
//int li,rl,lr; 
void pr(){
    ans++;
    if(ans <= 3){
        for(int i = 1;i <= n;i++){
            printf("%d ",s[i]);
        }
        printf("\n");
    }
}//输出 
double log2(int x){
    return log(x) / log(2);
}//求log2(x),即x的位数 
void queen(int x,int li,int lr,int rl){
    //在第x行找第x个皇后，li为列的被控制二进制位，lr为从左上到右下的被控制位
    //rl为从右上到左下的被控制位 
    if(x > n){
        pr();
        return;
    }//输出 
    int z = li | lr | rl;//所有被选的列，即被控制的列数 
    z = z ^ ((1 << n) - 1);//取反，找到未被控制的列数 
    z = z & ((1 << n) - 1);//取二进制后n位，去除超过n位的数，即越位的数 
    while(z){//枚举未被控制的列数 
        int y = z & (-z);//找一个未被控制的列数 
        int l = int(log2(y)+1);//算出是第几列 
        s[x] = l;//选进输出数组 
        queen(x+1,li|y,(lr|y)>>1,(rl|y)<<1);
        //dfs找下一个皇后
        //li列控制加上第l列的控制，lr左上右下控制加上第l列控制并在下一行右移一位
        //rl右上左下控制加上第l列控制并在下一行左移 
        z -= (z & (-z));//找过的列数去掉 
    }
}
int main(){
    freopen("checker.in","r",stdin);
    freopen("checker.out","w",stdout);
    scanf("%d",&n);
    queen(1,0,0,0); 
    printf("%d\n",ans);
    
    return 0;
}