首先，模 $2$ 就是行列式的值。

我们考虑容斥，钦定某些列没有数被选，那么有

$$\text{perm } A = (-1)^n \sum_{x \in \{0,1\}^n} (-1)^{x_1+x_2+\cdots +x_n} \prod _{i=1}^n (Ax)_i$$

也就是钦定某些列不选，然后每一行任意选一个数。

由于后面有一个 $\prod$ ，也就是说一个 $x$ 会造成贡献当且仅当 $Ax$ 中 $0$ 的个数小于等于 $1$ 。

于是我们考虑 $Ax$ 由于只有最多一个位置为 $0$ ，它只有 $n+1$ 种不同的值。所以我们可以枚举所有 $Ax$ 的取值，然后反解出所有 $x$ ，然后再代入 $x$ 求出值。

但是合法的 $x$ 的种类数可能很大，直接解这个东西复杂度是指数级的。

所以我们可以给这个矩阵加一行一列，得到：

$$\left(\begin{array}{ccccc} A_{1,1} & A_{1,2} & \cdots & A_{1, n} & v_{1} \\ A_{2,1} & A_{2,2} & \cdots & A_{2, n} & v_{2} \\ \vdots & & & & \vdots \\ A_{n, 1} & A_{n, 2} & \cdots & A_{n, n} & v_{n} \\ 0 & 0 & 0 & 0 & 1 \end{array}\right)$$

显然这个矩阵的积和式等于原矩阵。

如果我们随机取一个向量 $v$ 整进去，那么对于一个确定的 $Ax$ ，每一组 $x$ 成为它的解的概率都是 $\frac 1 {2^n}$ ，因为 $v$ 翻转一位一定会导致 $x$ 改变一位，而 $v$ 是随机选取的。又由于 $x$ 一共有 $2^n$ 种，所以 $Ax$ 的解期望有 $O(1)$ 个。

时间复杂度 $O(n^4)$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "ctime"
#include "queue"
#include "bitset"
using namespace std;
#define MAXN 306
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;

char ch[MAXN];
bitset<MAXN> A[MAXN] , a[MAXN];

int ok[MAXN];
int X[MAXN];

vi fre;
int re = 0;
void dfs( int s ) {
	if( s == fre.size() ) {
		per( i , n , 1 ) {
			int flg = 0 , ra = A[i][n + 1];
			rep( j , 1 , n ) if( A[i][j] ) {
				if( !flg ) flg = j;
				else 
					ra ^= X[j];
			}
			if( flg ) {
				X[flg] = ra;
			} else if( A[i][n + 1] ) return;
		}
		int tmp = 1 , sr = 0;
//		cout << A[2][3] << endl;
		rep( i , 1 , n ) {
			sr ^= X[i];
			int t = 0;
			rep( j , 1 , n ) if( X[j] ) 
				t = ( t + a[i][j] & 3 );
			tmp = tmp * t & 3;
		}
		tmp &= 3;
		if( sr ) tmp = 4 - tmp & 3;
		re += tmp;
	} else 
		rep( k , 0 , 1 ) X[fre[s]] = k , dfs( s + 1 );
}

int wkr( ) {
	rep( i , 1 , n ) A[i] = a[i];
	int cur = 1;
	rep( i , 1 , n ) {
		while( cur <= n ) {
			int flg = 0;
			rep( j , i , n ) if( A[j][cur] ) {
				if( i != j ) swap( A[j] , A[i] );
				flg = 1;
				break;
			}
			if( flg ) break;
			++ cur;
		}
		if( cur > n ) break;
		rep( j , i + 1 , n ) if( A[j][cur] ) A[j] ^= A[i];
		++ cur;
	}
	rep( i , 1 , n ) ok[i] = 0;
	rep( i , 1 , n ) {
		int flg = 0;
		rep( j , 1 , n ) if( A[i][j] ) { 
			ok[j] = 1; break;
		}
	}
	fre.clear();
	rep( i , 1 , n ) if( !ok[i] ) fre.pb( i );
	re = 0;
	dfs( 0 );
	return re;
}

void solve() {
	scanf("%d",&n);
	rep( i , 1 , n + 1 ) rep( j , 1 , n + 1 ) a[i][j] = A[i][j] = 0;
	rep( i , 1 , n ) {
		scanf("%s",ch + 1);
		rep( j , 1 , n ) a[i][j] = ch[j] - '0';
	} 
	rep( i , 1 , n ) a[i][n + 1] = rand() & 1;
	a[n + 1][n + 1] = 1;
	++ n;
//	rep( i , 1 , n ) {
//		rep( j , 1 , n ) printf("%d ",a[i].test(j)); puts("");
//	}
	rep( i , 1 , n ) a[i][n + 1] = 1;
	int res = 0;
	res += wkr( );
	rep( i , 1 , n ) {
		a[i][n + 1] = 0;
		res += wkr( );
		a[i][n + 1] = 1;
	}
	res %= 4;
	res = ( n & 1 ) ? 4 - res : res;
//	printf("%d\n",res % 4);
	puts( res % 4 ? "NO" : "YES" );
}

signed main() {
//	freopen("2.in","r",stdin);
	srand( time(0) );
    int T;cin >> T;while( T-- ) solve();
//    solve();
}