Groups Educational Codeforces Round 115 Solution

Introduction

Educational Codeforces rounds are organized by Codeforces for the Division 2 Coders. Similarly Educational Codeforces Round was held on   Sunday, October 10, 2021 at 14:35UTC+5.5 

Series of Educational Rounds continue to be held as Harbour Space University initiative. This round will be rated for coders with rating upto 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the full correct solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution. You will be given 7 problems and two hours to solve them. 

The contest was a success and lots of submissions were made by the hard striving coders. Problem A that is the Computer Game was very easy and had the maximum number of successful submission. Problem B was a not easy but not difficult also it was fit for an average coder to solve. Problem C although was quite confusing at the start but it needed good logic to solve it. Problem D was medium to difficult if you spot the logic then it was not a very big deal. Problem E was difficult to understand but the announcement that was made during the contest helped to understand the problem but it was still difficult to solve as an average coder. Problem F and G were very difficult and were made for the top coders to solve although problem G had only 2 successful submission which decided the rankings of the contest.

This Educational Rounds are very beneficial for the coders who just have started their coding journey and are yet to understand difficult logics and algorithms. Thus practice properly and it would be a great deal to coding journey. 

Question

n students attended the first meeting of the Berland SU programming course (n is even). All students will be divided into two groups. Each group will be attending exactly one lesson each week during one of the five working days (Monday, Tuesday, Wednesday, Thursday and Friday), and the days chosen for the groups must be different. Furthermore, both groups should contain the same number of students.

Each student has filled a survey in which they told which days of the week are convenient for them to attend a lesson, and which are not.

Your task is to determine if it is possible to choose two different week days to schedule the lessons for the group (the first group will attend the lesson on the first chosen day, the second group will attend the lesson on the second chosen day), and divide the students into two groups, so the groups have equal sizes, and for each student, the chosen lesson day for their group is convenient.

Input

The first line contains a single integer t$t$ (1≤t≤104) — the number of testcases.

Then the descriptions of t testcases follow.

The first line of each testcase contains one integer n (2≤n≤1000) — the number of students.

The i-th of the next n lines contains 5 integers, each of them is 0 or 1. If the j-th integer is 1, then the i-th student can attend the lessons on the j-th day of the week. If the j-th integer is 0, then the i-th student cannot attend the lessons on the j-th day of the week.

Additional constraints on the input: for each student, at least one of the days of the week is convenient, the total number of students over all testcases doesn't exceed 105.

Output

For each testcase print an answer. If it's possible to divide the students into two groups of equal sizes and choose different days for the groups so each student can attend the lesson in the chosen day of their group, print "YES" (without quotes). Otherwise, print "NO" (without quotes).

Example

input

Copy

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

output

Copy

YES
NO

Note

In the first testcase, there is a way to meet all the constraints. For example, the first group can consist of the first and the third students, they will attend the lessons on Thursday (the fourth day); the second group can consist of the second and the fourth students, and they will attend the lessons on Tuesday (the second day).

In the second testcase, it is impossible to divide the students into groups so they attend the lessons on different days.

Explanation

This problem is not very difficult. We are doing this problem the brute force way. First we take the inputs as given in the problem above. We run 3 nested loops two of size 5 and one of size as input n.

Now we take the union of numbers and then subtract to get the intersection of times thus we found the ways to divide the students according to their attending time. That's all now code it. Below code for C++ is given. I recommend not to copy paste the code, do it yourself. If you face problem in doing you can see the hints and ahead further. 

Program Code in C++

 #include<bits/stdc++.h>

using namespace std;

#define ll long long

void solve(){

    int n;

    cin>>n;

    int arr[n][5];

    for(int i=0;i<n;i++){

        for(int j=0;j<5;j++)

            cin>>arr[i][j];

    }

    for(int i=0;i<5;i++){

        for(int j=i+1;j<5;j++){

            int c1=0,c2=0,c3=0;

            for(int k=0;k<n;k++){

                if(arr[k][i]==1)

                    c1++;

                if(arr[k][j]==1)

                    c2++;

                if(arr[k][j]==1 && arr[k][i]==1)

                    c3++;

            }

            c1-=c3;

            c2-=c3;

            if(c1<=n/2 && c2<=n/2 && c1+c2+c3==n){

                cout<<"YES"<<endl;

                return;

            }

        }

    }

    cout<<"NO"<<endl;

}

int main(){

    

    ll t=1;

    cin>>t;

    while(t--){

        solve();

    }

}

Thus we come to the end of this solution, hope you got benefit from this solution.