Once N boys and M girls attended a party. You are given a matrix A of N rows and M columns where Aij is 1 if the i-th boy likes the j-th 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.

Difficulty: interview

Starter code:

Solutions:
for i in range(int(input())):
 n,k=map(int,input().split())
 m=[]
 for j in range(n):
  l=list(input())
  m.append(l)
 a=0
 for k in range(k):
  b=0
  for p in range(n):
   if m[p][k]=='1':
    b+=1
  if b>1:
   a+=((b*(b-1))//2)
 print(a)

a=int(input())
for i in range(a):
 n,m=map(int,input().split())
 b=[]
 for j in range(n):
  j=list(input())
  b.append(j)
 c=0
 for k in range(m):
  d=0
  for p in range(n):
   if b[p][k]=='1':
    d+=1
  if d>1:
   c+=((d*(d-1))//2)
 print(c)

# cook your dish here
w=int(input())
for i in range(w):
 B,f=list(map(int,input().split()))
 v =[]
 for j in range(B):
  j=list(input())
  v.append(j)
 q=0
 for k in range(f):
  s=0
  for n in range(B):
   if v[n][k]=='1':
    s+=1
  if s>1:
   q+=((s*(s-1))//2)
 print(q)
  


# cook your dish here
for i in range(int(input())):
 n,m=map(int,input().split())
 matrix = []
 for i in range(n):
  row = []
  s = input()
  for i in s:
   row.append(i)
  matrix.append(row)
 ans = 0
 for i in range(m):
  c= 0
  for j in range(n):
   if(matrix[j][i]=='1'):
    c+=1
  ans +=(c*(c-1)//2)
 print(ans)

T=int(input())
for i in range(T):
 B,G=list(map(int,input().split()))
 l=[]
 for j in range(B):
  m=list(input())
  l.append(m)
 d=0
 for k in range(G):
  c=0
  for n in range(B):
   if l[n][k]=='1':
    c+=1
  if c>1:
   d+=((c*(c-1))//2)
 print(d)


T=int(input())
for i in range(T):
 B,G=list(map(int,input().split()))
 l=[]
 for j in range(B):
  m=list(input())
  l.append(m)
 d=0
 for k in range(G):
  c=0
  for n in range(B):
   if l[n][k]=='1':
    c+=1
  if c>1:
   d+=((c*(c-1))//2)
 print(d)
 



for t in range(int(input())):
 n, m = list(map(int, input().split()))
 matrix = []
 for i in range(n):
  matrix.append(list(input()))
 colli = 0
 for i in range(m):
  count = 0
  for j in range(n):
   if matrix[j][i] == '1':
    count += 1
  if count > 1:
   colli += ((count * (count-1)) // 2)
 print(colli)


# cook your dish here
t = int(input())
for _ in range(t):
 n, m = map(int, input().split())
 matrix = []
 for i in range(n):
  matrix.append(list(input()))
 collision = 0
 for i in range(m):
  count = 0
  for j in range(n):
   if matrix[j][i] == '1':
    count += 1
  # print('Count:', count)
  if count > 1:
   collision += ((count * (count-1)) // 2)
 print(collision)

t = int(input())
for _ in range(t):
 n, m = map(int, input().split())
 matrix = []
 for i in range(n):
  matrix.append(list(input()))
 collision = 0
 for i in range(m):
  count = 0
  for j in range(n):
   if matrix[j][i] == '1':
    count += 1
  # print('Count:', count)
  if count > 1:
   collision += ((count * (count-1)) // 2)
 print(collision)

def factorial(n):
 fact = 1
 for i in range(1, n+1):
  fact = fact * i
 return fact
t = int(input())
for _ in range(t):
 n, m = map(int, input().split())
 matrix = []
 for i in range(n):
  matrix.append(list(input()))
 collision = 0
 for i in range(m):
  count = 0
  for j in range(n):
   if matrix[j][i] == '1':
    count += 1
  # print('Count:', count)
  if count > 1:
   collision += ((count * (count-1)) // 2)
 print(collision)

for _ in range(int(input())):
 N,M = (list(map(int,input().split(' '))))
 grid = []
 
 
 for x in range(N):
  row = [i for i in input()]
  grid.append(row)
 
 collisions = 0
 
 for x in range(M):
  z = 0
  for y in range(N):
   if grid[y][x] == '1':
    z += 1
  if z == 2:
   collisions += 1
  elif z > 2:
   collisions += (z * (z - 1)) // 2
 print(collisions)
  
 


# cook your dish here

def collisions(ar, n, m):
 res = 0
 for i in range(m):
  tem1, tem2 = 0, 0
  for j in range(n):
   if ar[j][i] == '1':
    tem1 += tem2
    tem2 += 1
  res += tem1
 return res

def __starting_point():
 t = int(input())
 for i in range(t):
  n, m = map(int, input().split())
  ar = []
  for i in range(n):
   ar.append(list(input()))
  print(collisions(ar, n, m))
__starting_point()

for _ in range(int(input())):
 m,n=map(int,input().split())
 l=[]
 for i in range(m):
  s=input()
  l.append(s)
 final=0
 for i in range(n):
  count=0
  for j in range(m):
   if l[j][i]=='1':
    count+=1
  if count>1:
   for k in range(count):
    final+=k
 print(final)

tc = int(input())
while tc !=0:   
 r,c = map(int, input().split())
 arr= []
 for i in range(r):
  temp = list(map(int, input()))
  arr.append(temp)
 count = 0
 for j in range(c):
  temp = 0
  for i in range(r):
   if arr[i][j]==1:
    temp += 1
  if temp!=1 and temp!=0:
   count += (temp*(temp-1))//2
 print(count)

 tc -= 1

# cook your dish here
t=int(input())
while t>0:
 n,m=map(int,input().split())
 l=[]
 co=0
 for i in range(n):
  l.append(input())
 for i in range(m):
  c=0
  for j in range(n):
   if l[j][i]=="1":
    c+=1
  co+=c*(c-1)/2
 print(int(co))
 t-=1

def comb(n, r):
 an = fact(n)
 an = an/fact(r)
 an = an/fact(n-r)
 
 return int(an)
 
def fact(n):
 ans = 1
 while(n>1):
  ans = ans*n
  n -= 1
 return ans
 
t = int(input())

for _ in range(t):
 n, m = [int(x) for x in input().split()]
 
 a = []
 ans = 0
 
 for i in range(n):
  temp = [int(x) for x in input()]
  a.append(temp)
 
 for i in range(m):
  c = 0
  for j in range(n):
   if(a[j][i] == 1):
    c += 1
  if(c>=2):
   ans += comb(c, 2)
 
 print(ans)

# cook your dish here
try:
 for _ in range(int(input())):
  n, m = map(int, input().split())
  l = []
  for j in range(n):
   l.append(list(input()))
  ans = []
  c = 0
  for u in range(m):
   for v in range(n):
    if l[v][u] == '1':
     c += 1
   ans.append(c)
   c = 0
  count = 0
  for j in range(len(ans)):
   count += ((ans[j] - 1) * (ans[j])) //2
  print(count)
except:
 pass

t=int(input())
for i in range(t):
 n,m=map(int,input().split())
 l=[]
 for j in range(n):
  l.append(list(input()))
 ans=[]
 c=0
 for u in range(m):
  for v in range(n):
   if l[v][u]=='1':
    c=c+1
  ans.append(c)
  c=0
 count=0
 for j in range(len(ans)):
  count=count+(((ans[j]-1)*(ans[j]))//2)
 print(count)

def fact(i):
 a = i
 while a > 1:
  i += (a-1)
  a = a - 1
 return i

for _ in range(int(input())):
 n, m = list(map(int, input().split()))
 matrix = [0] * m
 for _ in range(n):
  s = input()
  for i in range(len(s)):
   if s[i] == '1':
    matrix[i] += 1
 coll = [fact(matrix[i]-1) for i in range(m) if matrix[i] > 1]
 print((sum(coll) if coll else 0))# cook your dish here


def fact(i):
 a = i
 while a > 1:
  i += (a-1)
  a = a - 1
 return i

for _ in range(int(input())):
 n, m = list(map(int, input().split()))
 matrix = [0] * m
 for _ in range(n):
  s = input()
  for i in range(len(s)):
   if s[i] == '1':
    matrix[i] += 1
 coll = [fact(matrix[i]-1) for i in range(m) if matrix[i] > 1]
 print((sum(coll) if coll else 0))# cook your dish here


t=int(input())
for i in range(t):
 n,m=list(map(int,input().split()))
 l=[]
 for j in range(n):
  l.append(list(input()))
 ans=[]
 c=0
 for u in range(m):
  for v in range(n):
   if l[v][u]=='1':
    c=c+1
  ans.append(c)
  #print(ans)
  c=0
 count=0
 for j in range(len(ans)):
  count=count+(((ans[j]-1)*(ans[j]))//2)
 print(count)


t=int(input())
for i in range(t):
 n,m=list(map(int,input().split()))
 l=[]
 for j in range(n):
  l.append(list(input()))
 ans=[]
 c=0
 for u in range(m):
  for v in range(n):
   if l[v][u]=='1':
    c=c+1
  ans.append(c)
  c=0
 count=0
 for j in range(len(ans)):
  count=count+(((ans[j]-1)*(ans[j]))//2)
 print(count)


for _ in range(int(input())):
 n,m=map(int,input().split())
 matrix = []
 for i in range(n):
  row = []
  s = input()
  for ele in s:
   row.append(ele)
  matrix.append(row)
 ans = 0
 for i in range(m):
  cnt = 0
  for j in range(n):
   if(matrix[j][i]=='1'):
    cnt+=1
  ans +=(cnt*(cnt-1)//2)
 print(ans)