/*
2013腾讯马拉松初赛第5场
1005 郑厂长系列故事——N骑士问题
Time Limit: 3.0 Seconds Memory Limit: 65536K
郑厂长不是正厂长
也不是副厂长
他根本就不是厂长
还是那个腾讯公司的码农
一个业余时间喜欢下棋的码农
最近，郑厂长对八皇后问题很感兴趣，拿着国际象棋研究了好几天，终于研究透了。兴奋之余，坐在棋盘前的他又开始无聊了。无意间，他看见眼前的棋盘上只摆了八个皇后，感觉空荡荡的，恰好又发现身边还有几个骑士，于是，他想把这些骑士也摆到棋盘上去，当然棋盘上的一个位置只能放一个棋子。因为受八皇后问题的影响，他希望自己把这些骑士摆上去之后，也要满足每2个骑士之间不能相互攻击。
现在郑厂长想知道共有多少种摆法，你能帮助他吗？
骑士的下法：
每步棋先横走或直走一格，然后再往外斜走一格；或者先斜走一格，最后再往外横走或竖走一格（即走“日”字）。可以越子，没有"中国象棋"的"蹩马腿"限制。
Input
输入第一行为一个整数T(1<=T<=8)，表示有T组测试数据；
每组数据首先是一个整数N(1<=n<=10)，表示要摆N个骑士上去；
接下来是一个8*8的矩阵来描述一个棋盘，’.’表示这个位置是空的，’*’表示这个位置上已经放了皇后了；
数据中的初始棋盘保证是一个合法的八皇后摆法。
Output
对每组数据，请在一行内输出一个整数，表示合法的方案数。
Sample Input
2
1
*.......
....*...
.......*
.....*..
..*.....
......*.
.*......
...*....
2
*.......
....*...
.......*
.....*..
..*.....
......*.
.*......
...*....
Sample Output
56
1409
*/
/*
解题报告：
一看这数据范围就想到了状态压缩DP，由于马的攻击范围最多是上下2行。
所以我们只要管好前面两行的就行了，
dp[i][j][p][q]
表示第i行放马的状态是q,第i-1行的状态是p,前i行放马的个数是j个的种数。
推i+1行的时候枚举第i+1行放马的状态，进行转移。
总的复杂度无法估计，理论上是(1<<8)*(1<<8)*(1<<8)*n*8
这里需要一些剪枝，不然是通不过的。加了很多的非法判断。
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<list>
using namespace std;
typedef __int64 lld;
const int MAX = 10;
const int INF = 1000000000;
const double EPS = 1.0e-8;
const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
int dblcmp(double x) {
if(fabs(x
) < EPS
)return 0; return x < 0 ? -1 : 1;
}
int a[MAX];
lld dp[2][11][1 << 8][1 << 8];
char s[MAX];
bool ok1[1 << 8][1 << 8];
bool ok2[1 << 8][1 << 8];
bool judge(int a, int b, int d) {
int i;
int x, y;
for(i = 0; i + d - 1 < 8; i++) {
x = 1 << i;
y = 1 << i << d;
if((x & a) && (y & b))return false;
if((x & b) && (y & a))return false;
}
return true;
}
int cnt[1 << 8];
int count(int n) {
int ret = 0;
while(n) {
ret += n & 1;
n >>= 1;
}
return ret;
}
int main() {
int n = 6;
int i, j;
int k;
int T;
int CS = 1;
for(i = 0; i < (1 << 8); i++) {
for(j = 0; j < (1 << 8); j++) {
ok1[i][j] = judge(i, j, 1);
ok2[i][j] = judge(i, j, 2);
}
}
for(i = 0; i < (1 << 8); i++) {
cnt[i] = count(i);
// printf("cnt[%d]=%d\n",i,cnt[i]);
}
//printf("%d\n",1<<8);
while(T--) {
for(i = 0; i < 8; i++) {
a[i] = 0;
for(j = 0; j < 8; j++) {
a[i] *= 2;
if(s[j] == '*')a[i]++;
}
// printf("a[%d]=%d\n",i,a[i]);
}
int xx = 0;
for(i = 0; i < (1 << 8); i++) {
if(i & a[0])continue;
if(cnt[i] > n)continue;
dp[0][cnt[i]][0][i]++;
xx++;
//printf("i=%d\n",i);
}
// printf("xx=%d\n",xx);
int tag = 0;
for(i = 1; i < 8; i++) {
tag = i & 1;
for(xx = 0; xx <= n; xx++) {
for(j = 0; j < (1 << 8); j++) {
for(k = 0; k < (1 << 8); k++) {
dp[tag][xx][j][k] = 0;
}
}
}
for(j = 0; j < (1 << 8); j++) {
if(i - 2 >= 0 && (j & a[i - 2]))continue;
for(k = 0; k < (1 << 8); k++) {
if(k & a[i - 1])continue;
if(cnt[j] + cnt[k] > n)continue;
if(!ok2[j][k])continue;
int tt;
for(tt = cnt[j] + cnt[k]; tt <= n; tt++) {
if(dp[1 - tag][tt][j][k] == 0)continue;
for(int z = 0; z < (1 << 8); z++) {
if(cnt[z] + tt > n)continue;
if(z & a[i])continue;
if(!ok2[z][k] || !ok1[z][j])continue;
dp[tag][tt + cnt[z]][k][z] += dp[1 - tag][tt][j][k];
}
}
}
}
}
lld ans = 0;
for(i = 0; i < (1 << 8); i++) {
for(j = 0; j < (1 << 8); j++) {
//if(dp[tag][n][i][j]>0)printf("%d %d\n",i,j);
ans += dp[tag][n][i][j];
}
}
}
return 0;
}
/*
2
1
*.......
....*...
.......*
.....*..
..*.....
......*.
.*......
...*....
2
1
........
........
........
........
........
........
........
........
2
1
*******.
********
********
********
********
********
********
********
*/