Collisions

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Once N boys and M girls attended a party. You are given a matrix A of N rows and M columns where A_{ij} is 1 if the ith boy likes the jth girl, otherwise it will be 0. Note that it is not necessary that if a boy x likes girl y, then girl y should like boy x.
You know that if there are two different boys x and y, who both like girl z, then there will be a collision. Can you calculate the number of different collisions at this party? Note that order of boys in the collision doesn't matter.
Input
The first line contains a single integer T denoting the number of test cases. Then T test cases follow.
The first line of each test case contains two space separated integers N, M denoting the number of boys and girls, respectively.
Each of the following N lines contain M characters, each of them is either '0' or '1'.
Output
For each test case output a single line containing an integer corresponding to the number of collisions at the party.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N, M ≤ 10
Example
Input: 2 4 3 111 100 110 000 2 2 10 01 Output: 4 0
Explanation
Example Case 1. All three boys like the first girl, so there are (1, 2, 1), (1, 3, 1), (2, 3, 1) collisions with her. Boys 1 and 3 both like the second girl so this is one more collision. Only one boy likes the third girl, so there are no collisions with her and thus we have 4 collisions total.
Example Case 2. For each girl there is only one boy who likes her, so there are no collisions at all.
Author:  pavel1996 
Tester:  karanaggarwal 
Editorial  http://discuss.codechef.com/problems/LCOLLIS 
Tags  basicimplement, cakewalk, ltime37, pavel1996 
Date Added:  11062016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 