#include <iostream>
#include <cstring>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int g[N][N];
int col[N];
int n;
int ans;
int dy[3]={-1,0,1};
void dfs(int u)
{
    if(u>n){
    ans++;
    return;
    }
    if(col[u]==0){
        for(int i=0;i<3;i++)
        {
            if(i==0&&col[u-1]==1)
            continue;
            if(i==2&&col[u-1]==n)
            continue;
            col[u]=col[u-1]+dy[i];
            dfs(u+1);
            col[u]=0;
        }
    }
    else
    {
        if(abs(col[u]-col[...