Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shopping is Fun!!

By Riaz_BSMRSTU · Limits 3s, 512 MB

Mr. Hikiko passed his Eid without shopping because of ongoing lockdown. Now, Govt. removed the lockdown(assume) and it’s time to do some shopping. So, he came to the market and found some interesting thing here.

This market has only one shop and this shop has only one piece of every element. Now, n peoples came to the shop to do shopping and every person wants to buy some elements(maybe none). Any person will be satisfied if he can buy all the elements he need. Now the shop manager will choose exactly 3 persons and make them satisfied.

Your task is to find the number of way of choosing 3 persons, so that the shop manager can satisfy all of these 3 person. Two way will be count as different if at least one person differ in them.


Input will contain T (1 ≤ T ≤ 10) Test cases.
Each test case will start with two integer n (1 ≤ n ≤ 104), the number of persons and m (1 ≤ m ≤ 20), the number of elements on the shop.
Next, there will be n lines. Every line will contain m integers ai,j (0 ≤ ai,j ≤ 1).

If ai,j is 1: ith person wants to buy jth element.
If ai,j is 0: ith person doesn’t want to buy jth element.

Note: Sum of n over all test case won’t be bigger than 104.


For each test case, print the number of way.


5 3
1 0 1
1 0 0
0 1 0
0 1 0
0 0 1



67% Solution Ratio

YouKnowWhoEarliest, 1M ago

Gazi_MohaiminFastest, 0.2s

YouKnowWhoLightest, 4.3 MB

omar24Shortest, 1059B


Login to submit