#include <iostream>
using namespace std;

bool num[15][15];
int a[15];
int n;
int ans = 0;

bool check(int step, int clo)
{
    for (int i = 1; i < step; i++)
    {
        if (num[i][clo])return false;
    }
    int cur = 1;
    for (int i = step - 1; i >= 1; i--)
    {
        if ((clo + cur <= n &&num[i][clo + cur]) || (clo - cur > 0 && num[i][clo - cur])) return false;
        cur++;
    }
    return true;
}

void dfs(int step)
{
    if (step > n)
    {
        if (ans < 3)
        {
            for (int i = 1; i <= n; i++) printf("%d ", a[i]);
            printf("\n");
        }
        ans++;
        return ;
    }
    for (int i = 1; i <= n; i++)
    {
        num[step][i] = true;
        if (check(step, i))
        {
            a[step] = i;
            dfs(step + 1);
            a[step] = 0;
        }
        num[step][i] = false;
    }
}

int main()
{
    cin >> n;
    dfs(1);
    printf("%d\n", ans);
    return 0;
}