Xiao Q is a very clever child. Besides chess, he also enjoys playing a computer puzzle game called "Matrix Game." The game is played on an $N \times N$ black-and-white square grid (similar to a chessboard, but the colors are arbitrary). You can perform two types of operations on the matrix:

• Row swap operation: Choose any two rows of the matrix and swap them (i.e., swap the colors of the corresponding cells).
• Column swap operation: Choose any two columns of the matrix and swap them (i.e., swap the colors of the corresponding cells).

The goal of the game is to perform a sequence of operations such that all cells on the main diagonal (the line from the top-left corner to the bottom-right corner) of the square grid are black.

For some levels, Xiao Q is completely stumped, leading him to suspect that these levels might be unsolvable! Therefore, Xiao Q has decided to write a program to determine whether these levels have a solution.

Input

The first line contains an integer $T$, representing the number of test cases.

Each test case starts with an integer $N$, representing the size of the square grid. The next $N$ lines contain an $N \times N$ binary matrix (where $0$ represents white and $1$ represents black).

Output

The output should contain $T$ lines. For each test case, if the level has a solution, output Yes; otherwise, output No.

Constraints

• For 20% of the data, $N \le 7$.
• For 50% of the data, $N \le 50$.
• For 100% of the data, $N \le 200$.

Examples

Input 1

2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

Output 1

No
Yes