7875번 - (False) faces 다국어

문제

The Company is testing its brand new face recognition solution. The application is supposed to recognize people given their profiles. It is fed with a number of test cases to check if everything is working fine. Each test consists of 2n photos of n persons; there is a left profile and a right profile of each person in a single test case. The program matches left profiles with right profiles, but it is still far from perfect, so sometimes several right profiles are assigned to a single left profile (and vice versa). A consistent reconstruction is an assignment of different right profiles to all left profiles, such that all the pairs matched were proposed by the program.

The program output (on the left) and four possible consistent reconstructions.

In order to test the program, it is necessary to verify every possible consistent reconstruction. The verification has to be done by humans and the Company has a team of four experts who devoted their lives to face recognition. They are willing to do the job under one condition: their shares of work have to be equal, i.e., the number of consistent reconstructions has to be divisible by four. Your task is to check if it is so.

입력

The input contains several test cases. The first line of the input contains a positive integer Z ≤ 100, denoting the number of test cases. Then Z test cases follow.

The first line contains the number n of persons in a test (1 ≤ n ≤ 300). Then n lines follows, each containing n characters, each of them being 0 or 1. The j-th character in the i-th line is 1 if and only if the program matches the i-th left profile with the j-th right profile.

출력

The output should consist of one line containing YES if the number of reconstructions consistent with the program assignment is divisible by 4 and NO otherwise.

제한

힌트