Polygon is not only the best platform for developing problems but also a square matrix with side $n$, initially filled with the character 0.

On the polygon, military training was held. The soldiers placed a cannon above each cell in the first row and a cannon to the left of each cell in the first column. Thus, exactly $2n$ cannons were placed. [Image] Initial polygon for $n=4$. 

Cannons shoot character 1. At any moment of time, no more than one cannon is shooting. When a 1 flies out of a cannon, it flies forward (in the direction of the shot) until it collides with a polygon border or another 1. After that, it takes the cell in which it was before the collision and remains there. Take a look at the examples for better understanding.

More formally:   if a cannon stands in the row $i$, to the left of the first column, and shoots with a 1, then the 1 starts its flight from the cell ($i, 1$) and ends in some cell ($i, j$);  if a cannon stands in the column $j$, above the first row, and shoots with a 1, then the 1 starts its flight from the cell ($1, j$) and ends in some cell ($i, j$). 

For example, consider the following sequence of shots: [Image] 

 1. Shoot the cannon in the row $2$.                         2. Shoot the cannon in the row $2$.                         3. Shoot the cannon in column $3$. 

You have a report from the military training on your desk. This report is a square matrix with side length $n$ consisting of 0 and 1. You wonder if the training actually happened. In other words, is there a sequence of shots such that, after the training, you get the given matrix?

Each cannon can make an arbitrary number of shots. Before the training, each cell of the polygon contains 0.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 50$) — the size of the polygon.

This is followed by $n$ lines of length $n$, consisting of 0 and 1 — the polygon matrix after the training.

The total area of the matrices in all test cases in one test does not exceed $10^5$.


-----Output-----

For each test case print:  YES if there is a sequence of shots leading to a given matrix;  NO if such a sequence does not exist. 

The letters in the words YES and NO can be printed in any case.


-----Example-----
Input
5
4
0010
0011
0000
0000
2
10
01
2
00
00
4
0101
1111
0101
0111
4
0100
1110
0101
0111

Output
YES
NO
YES
YES
NO



-----Note-----

The first test case was explained in the statement.

The answer to the second test case is NO, since a 1 in a cell ($1, 1$) flying out of any cannon would continue its flight further.

Difficulty: introductory

Starter code:

Solutions:
def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


t = read_int()
for case_num in range(t):
    n = read_int()
    mat = []
    for i in range(n):
        mat.append(input())
    ok = True
    for i in range(n):
        for j in range(n):
            if mat[i][j] == '0':
                continue
            cok = j == n - 1 or i == n - 1
            if not cok:
                cok = mat[i][j + 1] == '1' or mat[i + 1][j] == '1'
            if not cok:
                ok = False
                break
        if not ok:
            break
    print('YES' if ok else 'NO')


import sys
input = sys.stdin.readline


t = int(input())
for _ in range(t):
    n = int(input())
    s = [input()[:-1] + "1" for i in range(n)] + ["1" * (n + 1)]
    flag = True
    for i in range(n):
        for j in range(n):
            if s[i][j] == "0":
                continue
            if s[i + 1][j] == "1" or s[i][j + 1] == "1":
                continue
            flag = False
    if flag:
        print("YES")
    else:
        print("NO")


T = int(input())

for _ in range(T):
    N = int(input())

    cell = [list(map(int, list(input()))) for _ in range(N)]

    def dfs(x, y):

        if x < 0 or y < 0:
            return

        if cell[y][x] == 0:
            return

        cell[y][x] = 0
        dfs(x, y - 1)
        dfs(x - 1, y)

    for x in range(N):
        dfs(x, N - 1)

    for y in range(N):
        dfs(N - 1, y)

    for c in cell:
        if max(c) == 1:
            print("NO")
            break
    else:
        print("YES")


T = int(input())

for t in range(T):
    N = int(input())
    M = []
    for i in range(N):
        row = input()
        M.append(row)

    for i in range(len(M)-1):
        for j in range(len(M[i])-1):
            if M[i][j] == '1' and M[i+1][j] == '0' and M[i][j+1] == '0':
                print('NO')
                break
        else:
            continue
        break
    else:
        print('YES')


import sys
T = int(sys.stdin.readline().strip())
for t in range(T):
    n = int(sys.stdin.readline().strip())
    arr = []
    for i in range(n):
        tmp = sys.stdin.readline().strip()
        arr.append(list(tmp))
    can = True
    for i in range(n-1):
        for j in range(n-1):
            if arr[i][j] == "1":
                if arr[i+1][j] == "0" and arr[i][j+1] == "0":
                    can = False
                    break
        if not can: break
    if can: print("YES")
    else: print("NO")

for _ in range(int(input())):
    n = int(input())
    ar = []
    for i in range(n):
        ar.append(list(map(int, input())))
    ans = 'YES'
    for i in range(n - 1):
        for j in range(n - 1):
            if ar[i][j] == 1:
                flag = 0
                if 0 <= i + 1 <= n - 1 and ar[i + 1][j] == 1:
                    flag = 1
                elif 0 <= j + 1 <= n - 1 and ar[i][j + 1] == 1:
                    flag = 1
                if flag == 0:
                    ans = 'NO'
                    break
    print(ans)

def isvalid(l,n):
    for i in range(n):
        for j in range(n):
            if(l[i][j]=='1' and i!=n-1 and j!=n-1 and l[i+1][j]=='0' and l[i][j+1]=='0'):
                return 0
    return 1
t=int(input())
for you in range(t):
    n=int(input())
    l=[]
    for i in range(n):
        s=input()
        l.append(s)
    if(isvalid(l,n)):
        print("YES")
    else:
        print("NO")


t=int(input())
for i in range(t):
    n=int(input())
    matrix=[]
    for j in range(n):
        s=input()
        matrix.append(s)
    failflag=0
    for x in range(n):
        for y in range(n):
            if matrix[x][y]=='1' and x<n-1 and y<n-1:
                if matrix[x+1][y]=='0' and matrix[x][y+1]=='0':
                    failflag=1
    if failflag==0:
        print('YES')
    else:
        print('NO')

import sys

cases = int(sys.stdin.readline())

for _ in range(cases):
    ''' inputs '''
    n = int(sys.stdin.readline())                         # single input
    # n, m = map(int, sys.stdin.readline().split())         # two inputs
    # A = list(map(int, sys.stdin.readline().split()))      # list input
    '''code here'''
    M = []
    for i in range(n):
        M.append(list(map(int, list(sys.stdin.readline().strip()))))
        
    res = True
    
    for i in range(n-1):
        for j in range(n-1):
            if M[i][j] == 1 and M[i+1][j] == 0 and M[i][j+1] == 0:
                res = False
                break
    
    print("YES" if res else "NO")


def main():
    import sys
    input = sys.stdin.readline
    for __ in [0]*int(input()):
        N = int(input())
        S = [tuple(map(int, input()[:-1])) for _ in [0]*N]

        for i in range(N-1):
            for j in range(N-1):
                if S[i][j] and S[i+1][j] == S[i][j+1] == 0:
                    print('NO')
                    break
            else:
                continue
            break
        else:
            print('YES')


def __starting_point():
    main()

__starting_point()

from math import *
import math

def r1(t):
    return t(input())

def r2(t):
    return [t(i) for i in input().split()]

def r3(t):
    return [t(i) for i in input()]

for zzz in range(r1(int)):
    n = r1(int)
    g = []
    for i in range(n):
        g.append(r3(int))

    ha = True

    for i in range(n - 1):
        for j in range(n - 1):
            if (g[i][j]) and (not g[i][j + 1]) and (not g[i + 1][j]):
                ha = False
                break
        if not ha:
            break

    if ha:
        print('YES')
    else:
        print('NO')