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

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.

Output

For each test case, print the number of way.

Sample

InputOutput
1
5 3
1 0 1
1 0 0
0 1 0
0 1 0
0 0 1
2

Discussion

Statistics


67% Solution Ratio

YouKnowWhoEarliest, 1M ago

Gazi_MohaiminFastest, 0.2s

YouKnowWhoLightest, 4.3 MB

omar24Shortest, 1059B

Submit

Login to submit