F - (False) faces

Time limit: 60 s
Memory limit: 32 MB

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 photos of 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.

Multiple Test Cases

The input contains several test cases. The first line of the input contains a positive integer , denoting the number of test cases. Then test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.

Single Instance Input

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

Single Instance Output

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

Example

Input

2
4
1100
1100
0011
0011
3
111
011
001

Output

YES
NO