Description

There are N(N is an even number) people in ZJUT. Each person in ZJUT loves some ones and hates the others. Is it possible to divide them to N/2 groups in which the two people love each other?

Input

The first line gives a number T, means the number of test cases. The first line of each test case gives a number N, and then follows a N*N matrix. The elements of the matrix are either 0 or 1. If the j-th number in the i-th row is 1, it means the i-th person loves the j-th person, else he doesn’t love him. N,T <= 16

Output

If it is possible to divide them, print “Yes”, else print “No”.

Sample

Input

2
4
1 1 1 0
1 1 0 1
1 1 1 0
0 1 0 1
4
1 1 0 0
0 1 0 1
1 0 1 0
0 0 1 1

Output

Yes
No

Source: lily