#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define FF(i, a, b) for(int i=a; i=b; i--) #define REP(i, n) for(int i=0; i edges; vector G[maxn]; vector g[maxn]; int n, ncase, color[maxn], flag, d[maxn], cnt[maxn]; bool inq[maxn]; char ch[maxn][maxn]; void init() { REP(i, n) G[i].clear(), g[i].clear(); edges.clear(); CLR(color, 0); } void add(int a, int b, int c) { edges.PB((Edge){a, b, c}); int nc = edges.size(); G[a].PB(nc-1); } void dfs(int u, int c) //二分染色 { color[u] = c; int nc = g[u].size(); REP(i, nc) { int v = g[u][i]; if(!color[v]) dfs(v, 3-c); } } bool spfa() { queue q; REP(i, n) d[i] = cnt[i] = 0, inq[i] = 1, q.push(i); while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; REP(i, G[u].size()) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; if(!inq[e.to]) { q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; } } } } return false; } bool solve() { //判奇圈 REP(i, n) if(!color[i]) dfs(i, 1); REP(i, n) REP(j, g[i].size()) if(color[i] == color[g[i][j]]) return 0; REP(i, n) { FF(j, i+1, n) { if(ch[i][j] == '1') { if(color[i] == 1) add(i, j, -T); else add(j, i, -T); } else { if(color[i] == 1) add(j, i, T-1); else add(i, j, T-1); } } } if(spfa()) return 0; return 1; } int main() { scanf("%d", &ncase); while(ncase--) { init(); scanf("%d", &n); REP(i, n) { scanf("%s", ch[i]); REP(j, n) if(i != j && ch[i][j] == '1') g[i].PB(j); } if(solve()) puts("Yes"); else puts("No"); } return 0; }