The so-called love triangle, some refers to two people at the same time to fall in love with a person, and there is a person love two people at the same time. But the common triangle relationship is more complex, A love B~ and B love C~ but C love A, which can be described as the most painful feelings of the dispute. Want to put love, love can not.
These are all nonsense.
Among any three people (A,B and C) , A loves B, B loves C and C loves A.We called triangle love.To reject it,we need to know if there are triangle love.
The first line contains a single integer t (1 <= t <= 15), the number of test cases.
For each case, the first line contains one integer N (0 < N <= 2000).
In the next N lines contain the adjacency matrix A of the relationship (without spaces). Ai,j = 1 means i-th people loves j-th people, otherwise Ai,j = 0.
It is guaranteed that the given relationship is a tournament, that is, Ai,i= 0, Ai,j ≠ Aj,i(1<=i, j<=n,i≠j).
For each case, output the case number as shown and then print “Yes”, if there is a “Triangle Love” among these N people, otherwise print “No”.
Take the sample output for more details.
2
5
00100
10000
01001
11101
11000
5
01111
00000
01000
01100
01110Case #1: Yes
Case #2: No