{"raw_statement":[{"iden":"problem statement","content":"You are given $N$ strings $S_1, \\ldots, S_N$, each of length $N$, consisting only of `0` and `1`. Let $S_{i,j}$ denote the $j$\\-th character of $S_i$. It is guaranteed by the constraints that there exists at least one integer pair $(i, j)$ satisfying $S_{i,j} = $ `1`.\nTakahashi and Aoki play the following game:\n\n1.  Takahashi chooses one integer pair $(i, j)$ satisfying $1 \\leq i, j \\leq N$ and $S_{i,j} = $ `1`.\n2.  Aoki asks Takahashi at least $0$ and at most $N$ questions. In each question, Aoki chooses an integer pair $(i', j')$ satisfying $1 \\leq i', j' \\leq N$, and Takahashi tells Aoki whether \"At least one of $i = i'$ or $j = j'$ holds\" is true or false.\n3.  Aoki guesses $(i, j)$. If his guess is correct, Aoki wins; otherwise, he loses.\n\nAoki knows the possible choices of $(i, j)$ that Takahashi can choose, that is, he knows $S_1, \\ldots, S_N$ before playing the game. Also, in step 2, Aoki can choose $(i', j')$ based on the answers to previous questions.\nDetermine whether Aoki can always win the game regardless of Takahashi's choice of $(i, j)$ and randomness, if he uses an appropriate strategy.\nThere are $T$ test cases in each input."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $1 \\leq N \\leq 500$\n*   The sum of $N^2$ over all test cases in each input is at most $500^2$.\n*   $S_i$ is a string of length $N$ consisting of `0` and `1`.\n*   There is at least one integer pair $(i, j)$ satisfying $S_{i,j} = $ `1`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$N$\n$S_1$\n$\\vdots$\n$S_N$"},{"iden":"sample input 1","content":"3\n2\n01\n11\n2\n11\n11\n10\n0101011110\n1100100001\n1101100000\n0111101010\n1000011001\n1110101010\n1110110100\n1110000110\n0000001011\n1001111100"},{"iden":"sample output 1","content":"Yes\nNo\nYes\n\nIn the first test case, an example of the game is as follows:\n\n1.  Takahashi chooses $(i, j) = (2, 2)$ satisfying $S_{i,j}=\\ $ `1`.\n2.  Aoki asks two questions. In the first question, he chooses $(i', j') = (1, 1)$. Takahashi tells him that \"At least one of $i = 1$ or $j = 1$ holds\" is false. In the second question, he chooses $(i', j') = (2, 2)$. Takahashi tells him that \"At least one of $i = 2$ or $j = 2$ holds\" is true.\n3.  Aoki guesses $(i, j) = (2, 2)$. Since his guess is correct, Aoki wins.\n\nThis is just an example of the game, and Aoki's strategy might not be optimal. However, if Aoki uses an appropriate strategy, he can always win the game, so the output for the first test case is `Yes`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}