#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int visx[15], visy[15], vis1[30], vis2[30], n;
vector<int> a;
// 判断 x,y 能不能放
bool check(int x, int y)
{
if(visx[x] == 1)return false;
if(visy[y] == 1)return false;
if(vis1[y - x + n] == 1)return false;
if(vis2[x + y] == 1)return false;
return true;
}
int cnt;
void dfs(int deep)
{
if(deep == n + 1){
cnt++;
if(cnt <= 3){
for(int i = 0; i < n; i++)cout << a[i] << " ";
cout << '\n';
}
return;
}
for(int i = 1; i <= n; i++)
{
if(!check(deep, i))continue;
visx[deep] = 1;
visy[i] = 1;
vis1[i - deep + n] = 1;
vis2[i + deep] = 1;
a.push_back(i);
dfs(deep + 1);
a.pop_back();
visx[deep] = 0;
visy[i] = 0;
vis1[i - deep + n] = 0;
vis2[i + deep] = 0;
}
}
int main()
{
cin >> n;
dfs(1);
cout<<cnt<<'\n';
}
