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).

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

Submit

Login to submit.

Statistics

67% Solution Ratio
YouKnowWhoEarliest, Jun '20
Kuddus.6068Fastest, 0.1s
YouKnowWhoLightest, 4.3 MB
omar24Shortest, 1059B
Toph uses cookies. By continuing you agree to our Cookie Policy.