Description

这几天，子浩君潜心研究线性代数。 行列式的值定义如下：

其中，τ（j1j2...jn)为排列j1j2...jn的逆序数。

子浩君很厉害的，但是头脑经常短路，所以他会按照行列式值的定义去计算，这个行列式子浩君也还是能算对的。但是，在计算的过程中，如果出现连续三行选取的元素为83(S)，83(S)，82(R)的话，子浩君会忍不住拿走它们:-D，然后这三个数的乘积将被视为1，而其它数值计算不变。那么在子浩君的计算下，最后得到的行列式的值会为多少呢？

Input

数据第一行为一个整数T（T<=50）。 接下来有T组测试数据，每组数据开始有一个整数n（2<=n<=8）。 接下来有n行数字，每行有n个数字，第ith行第jth个数字代表矩阵的第ith行第jth列的数字，保证每个数字在int范围内的非负整数。

Output

输出一个整数，保证在[-(2^63-1), 2^63-1]范围内，即使在子浩君计算过程中也是。

Sample Input

4

2
1 1
0 1

3
83 1 1
0 83 1
0 0 82

3
83 1 1
0 82 1
0 0 83

3
83 1 1
0 83 1
0 1 82

Sample Output

1
1
564898
-82

Hint

例如，当子浩君遇到 a11 * a22 * a33 * a44 = 83 * 83 * 82 * 1，会计算成 1 * 1 = 1，而 83 * 82 * 83 * 1或者 83 * 83 * 1 * 82则不会改变运算规则
数据范围比较小，可以直接暴力 
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
ll per[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };
ll matri[10][10];
ll n;
ll check()//逆序数判断
{
	ll cnt = 0;
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n;j++)
		if (per[j] < per[i])
			cnt++;
	}
	if (cnt & 1)
		return -1;
	else
		return 1;
}
int main()
{
	int T;
	while (cin >> T)
	{
		while (T--)
		{
			cin >> n;
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					cin >> matri[i][j];
				}
			}
			ll res = 0;
			do//先进行一次操作然后再全排
			{
				ll tmp = 1;
				for (int i = 0; i < n; i++)
				{
					
					if (i<n-2&&matri[i][per[i]] == 83 && matri[i + 1][per[i + 1]] == 83 && matri[i + 2][per[i + 2]]==82)
						i += 2;
					else
						tmp *= matri[i][per[i]];
				}
				tmp*=check();
				res += tmp;
			}while (next_permutation(per,per + n));
			cout << res << endl;
		}
	}
	return 0;
}
/**********************************************************************
	Problem: 1979
	User: leo6033
	Language: C++
	Result: AC
	Time:284 ms
	Memory:2024 kb
**********************************************************************/