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.

Source: codechef | Difficulty: EASY
Tags: Implementation

Complete search


Solutions:
t = int(input())
while t:
	(n, m) = map(int, input().split())
	ans = 0
	temp_list = [0] * m
	for i in range(n):
		temp_str = str(input())
		for j in range(m):
			if temp_str[j] == '1':
				temp_list[j] += 1
	for k in temp_list:
		ans += (k - 1) * k // 2
	print(ans)
	t -= 1


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


for t in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	A = []
	for i in range(N):
		A.append(list(input()))
	total_collision = 0
	for j in range(M):
		count = 0
		for i in range(N):
			count += int(A[i][j])
		collisions = int(count * (count - 1) / 2)
		total_collision += collisions
	print(total_collision)


def Factorial(num):
	Fac = 1
	for ele in range(1, num + 1):
		Fac *= ele
	return Fac
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	Like = []
	for ele in range(n):
		mylist = []
		num = input()
		for ch in num:
			mylist.append(int(ch))
		Like.append(mylist)
	Transpose = [[0 for x in range(n)] for y in range(m)]
	for ele in range(m):
		for ele2 in range(n):
			Transpose[ele][ele2] = Like[ele2][ele]
	Collision = 0
	for ele in Transpose:
		Total = sum(ele)
		if Total >= 2:
			Collision += Factorial(Total) / (Factorial(2) * Factorial(Total - 2))
	print(int(Collision))


import itertools
t = int(input())
for t in range(t):
	(n, m) = [int(i) for i in input().split()]
	arr = []
	for i in range(n):
		arr.append(input())
	count = 0
	for i in range(m):
		for j in range(n):
			if arr[j][i] == '1':
				for k in range(j + 1, n):
					if arr[k][i] == '1':
						count += 1
	print(count)


T = int(input())
for _ in range(0, T):
	(n, m) = map(int, input().split())
	ln = []
	for i in range(0, n):
		lm = str(input())
		lm.split()
		ln.append(lm)
	col = 0
	for j in range(0, m):
		count = 0
		for i in range(0, n):
			if ln[i][j] == '1':
				count += 1
		if count > 1:
			col += count * (count - 1) // 2
	print(col)


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)


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)


tc = int(input())
for i in range(tc):
	(r, c) = map(int, input().split())
	ans = [0] * c
	cnt = 0
	for j in range(r):
		temp = list(map(int, input()))
		for k in range(len(temp)):
			if temp[k] == 1:
				ans[k] += 1
		temp = []
	for i in ans:
		cnt += i * (i - 1) // 2
	print(cnt)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	lst = []
	for i in range(n):
		a = []
		x = list(map(int, input()))
		for k in range(len(x)):
			a.append(x[k])
		lst.append(a)
		print()
	c = 0
	for i in range(m):
		r = 0
		for j in range(n):
			if lst[j][i] == 1:
				r += 1
		c += (r - 1) * r // 2
	print(c)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	arr = []
	for j in range(x):
		a = list(input())
		arr.append(a)
	sum = 0
	count = 0
	for k in range(y):
		for l in range(x):
			if l < x:
				if arr[l][k] == '1':
					count += 1
		sum += count * (count - 1) / 2
		count = 0
	print(int(sum))


for _ in range(int(input())):
	(b, g) = map(int, input().split())
	lis = []
	for i in range(b):
		s = list(input())
		s = map(int, s)
		lis.append(list(s))
	ans = 0
	for i in range(g):
		c = 0
		for j in range(b):
			if lis[j][i] == 1:
				c += 1
		ans += sum(range(1, c))
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(l1, s, su) = ([], [], 0)
	for i in range(n):
		l = list(map(int, input()))
		l1.append(l)
	for i in range(m):
		s = list()
		for j in range(n):
			s.append(l1[j][i])
		su += sum([i for i in range(s.count(1))])
	print(su)


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)


tests = int(input())
for i in range(tests):
	(rows, cols) = map(int, input().split())
	likes_arr = [0] * cols
	for j in range(rows):
		temp_arr = list(input())
		for k in range(cols):
			likes_arr[k] += int(temp_arr[k])
	ans = 0
	for j in likes_arr:
		if j > 1:
			top = 1
			for x in range(j - 1, j + 1):
				if x > 0:
					top *= x
			ans += top // 2
	print(ans)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l1 = [0 for i in range(m)]
	for i in range(n):
		l = list(map(int, list(input())))
		for j in range(m):
			l1[j] += l[j]
	ans = 0
	for i in l1:
		ans += i * (i - 1) // 2
	print(ans)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	ans = 0
	arr = []
	for _ in range(r):
		arr.append(input())
	for j in range(c):
		count = 0
		for i in range(r):
			if int(arr[i][j]) == 1:
				count += 1
		ans += count * (count - 1) // 2
	print(ans)


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
		if count > 1:
			collision += count * (count - 1) // 2
	print(collision)


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


def coll(n):
	s = 0
	for i in range(1, n):
		s += i
	return s
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [0] * m
	for _ in range(n):
		r = input()
		for i in range(len(r)):
			if r[i] == '1':
				l[i] += 1
	collision = 0
	for k in l:
		if k > 2:
			collision += coll(k)
		if k == 2:
			collision += 1
	print(collision)


t = int(input())
for i in range(t):
	a = input().strip().split(' ')
	(n, m) = (int(a[0]), int(a[1]))
	ans = 0
	l = [int(input()) for i in range(n)]
	for i in range(m):
		cc = 0
		for j in range(n):
			if l[j] % 2 != 0:
				cc += 1
			l[j] = l[j] // 10
		if cc != 0:
			ans = ans + cc * (cc - 1) // 2
	print(ans)


from math import comb
t = int(input())
for ni in range(t):
	(n, m) = map(int, input().split())
	l = [0] * m
	for nj in range(n):
		a = input()
		for i in range(len(a)):
			l[i] = int(l[i]) + int(a[i])
	count = 0
	for i in l:
		count = count + comb(i, 2)
	print(count)


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())
while t > 0:
	(n, k) = map(int, input().split())
	lst = [0] * k
	while n > 0:
		strg = input()
		for i in range(0, k):
			if strg[i] == '1':
				lst[i] += 1
			i += 1
		n -= 1
	total = 0
	for i in range(0, k):
		total += lst[i] * (lst[i] - 1) // 2
		i += 1
	print(total)
	t -= 1


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


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


try:
	for _ in range(int(input())):
		(N, M) = map(int, input().split(' '))
		A = [input() for __ in range(N)]
		collisions = 0
		for col in range(M):
			count = 0
			for row in range(N):
				if A[row][col] == '1':
					count += 1
			collisions += count * (count - 1) // 2
		print(collisions)
except EOFError:
	pass


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


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)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = []
	for i in range(a):
		c += [input()]
	e = 0
	for i in range(b):
		d = 0
		for j in range(a):
			if c[j][i] == '1':
				d += 1
		e += d * (d - 1) / 2
	print(int(e))


t = int(input())
for i in range(t):
	(r, c) = list(map(int, input().split()))
	a = []
	for j in range(r):
		b = int(input())
		a.append(b)
	res = 0
	for j in range(c):
		p = 0
		for k in range(r):
			rem = a[k] % 10
			a[k] = a[k] // 10
			if rem == 1:
				p = p + 1
		res = res + p * (p - 1) // 2
	print(res)


def fact(n):
	if n <= 1:
		return 1
	else:
		return n * fact(n - 1)

def com(c):
	return fact(c) // (fact(2) * fact(c - 2))
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	A = [0 for i in range(n)]
	for i in range(n):
		A[i] = input()
	c = 0
	k = 0
	for j in range(m):
		c = 0
		for i in range(n):
			if A[i][j] == '1':
				c += 1
		k += com(c)
	print(k)


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


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	strings = list()
	for n in range(N):
		strings.append(input())
	collisions = 0
	for m in range(M):
		new_str = ''
		for s in strings:
			new_str += s[m]
		if new_str.count('1') > 2:
			for i in range(new_str.count('1')):
				collisions += i
		elif new_str.count('1') == 2:
			collisions += 1
	print(collisions)


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())
	l = []
	for i in range(n):
		l.append(input())
	collision = 0
	for i in range(m):
		cnt = 0
		for j in range(n):
			if l[j][i] == '1':
				cnt = cnt + 1
		collision = collision + cnt * (cnt - 1) // 2
	print(collision)


for _ in range(int(input())):
	(my_inputn, my_inputm) = [int(my_inputx) for my_inputx in input().split()]
	my_inputa = []
	my_inputc = 0
	for _ in range(my_inputn):
		my_inputa.append([int(i) for i in input()])
	for i in range(my_inputm):
		for j in range(my_inputn):
			if my_inputa[j][i] == 1:
				for k in range(j + 1, my_inputn):
					if my_inputa[k][i] == 1:
						my_inputc += 1
	print(my_inputc)


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 _ in range(int(input())):
	(m, n) = map(int, input().split())
	like = []
	for i in range(m):
		like.append(input())
	ans = 0
	for i in range(n):
		cur = 0
		for j in range(m):
			cur += 1 if like[j][i] == '1' else 0
		ans += cur * (cur - 1) // 2
	print(ans)


for W in range(int(input())):
	(N, M) = map(int, input().split())
	Ans = 0
	F = [1 for x in range(11)]
	F[0] = F[1] = 0
	for x in range(3, 11):
		F[x] *= x * (x - 1) // 2
	L = [[] for x in range(N)]
	for i in range(N):
		S = input()
		for ch in S:
			if ch == '0':
				L[i].append(0)
			else:
				L[i].append(1)
	for q in range(M):
		c1 = 0
		for i in range(N):
			if L[i][q]:
				c1 += 1
		Ans += F[c1]
	print(Ans)


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


t = int(input())

def fact(x):
	f = 1
	for i in range(2, x + 1):
		f *= i
	return f
while t > 0:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	y = n
	l = []
	while n > 0:
		l.append(input())
		n -= 1
	x = 0
	for i in range(0, m):
		c = 0
		for j in range(0, y):
			if l[j][i] == '1':
				c += 1
		if c > 1:
			x = x + fact(c) // fact(c - 2) // 2
	print(x)
	t -= 1


try:
	for a in range(int(input())):
		(n, m) = map(int, input().split())
		value = [0 for b in range(m)]
		for c in range(n):
			string = input()
			for i in range(m):
				if string[i] == '1':
					value[i] += 1
		ans = 0
		for j in value:
			ans += j * (j - 1) // 2
		print(ans)
except:
	pass


t = int(input())
for k in range(t):
	(a, b) = map(int, input().split())
	c = []
	for j in range(a):
		d = str(input())
		c.append(d)
	f = 0
	for i in range(b):
		e = 0
		for l in c:
			if l[i] == '1':
				e += 1
		if e > 1:
			n = 0
			for m in range(1, e):
				n += m
			f += n
	print(f)


t = int(input())
for i in range(1, t + 1):
	nm = list(map(int, input().split()))
	n = nm[0]
	m = nm[1]
	l = []
	collision = 0
	for j in range(1, n + 1):
		l.append(list(map(int, list(input()))))
	for k in range(0, m):
		c = 0
		for o in range(0, len(l)):
			if l[o][k] == 1:
				c = c + 1
		collision = collision + int(c * (c - 1) / 2)
	print(collision)


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)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	check = [0] * m
	for _ in range(n):
		st = input()
		for i in enumerate(st):
			if i[1] == '1':
				check[i[0]] += 1
	s = 0
	for i in check:
		s += i * (i - 1) // 2
	print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append([j for j in input()])
	req = []
	p = []
	for i in range(m):
		for j in range(n):
			p.append(arr[j][i])
		req.append(p)
		p = []
	ans = 0
	for i in range(m):
		a = req[i].count('1')
		if a >= 2:
			ans += (a - 1) * a // 2
	print(ans)


import numpy as np
T = int(input())
for tj in range(T):
	(N, M) = map(int, input().split())
	Matrix = np.zeros((N, M))
	for nj in range(N):
		Matrix[nj] = list(input())
	number_conflicts = 0
	for column in range(M):
		number_ones = 0
		for row in range(N):
			number_ones += int(Matrix[row][column])
		number_conflicts += number_ones * (number_ones - 1) / 2
	print(int(number_conflicts))


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)


import math

def ncr(n, r):
	return math.factorial(n) // math.factorial(r) // math.factorial(n - r) if n >= r else 0
for i in range(int(input())):
	((n, m), ans, a) = (map(int, input().split()), 0, [])
	for z in range(n):
		a.append(input())
	a = [[a[y][x] for y in range(len(a))] for x in range(len(a[0]))]
	for z in range(m):
		ans += ncr(a[z].count('1'), 2)
	print(ans)


n = int(input())
for i in range(n):
	(N, M) = map(int, input().split(' '))
	mat = []
	for i in range(N):
		mat.append(int(input()))
	col = 0
	for j in range(M):
		add = 0
		for k in range(N):
			if mat[k] // 10 ** (M - j - 1) == 1:
				add = add + 1
				mat[k] = mat[k] % 10 ** (M - j - 1)
		col = col + int(add * (add - 1) / 2)
	print(col)


import numpy as np
from itertools import combinations
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	L = []
	for i in range(N):
		x = list(map(int, list(input())))
		L.append(x)
	a = np.array(L).T
	c = 0
	for i in a:
		ones = i.sum()
		c += len(list(combinations(range(ones), 2)))
	print(c)


for _ in range(int(input())):
	a = [int(i) for i in input().split()]
	b = []
	for i in range(a[0]):
		c = input()
		b.append(c)
	ans = 0
	for i in range(0, a[0]):
		for j in range(i + 1, a[0]):
			for k in range(0, a[1]):
				if b[i][k] == '1' and b[j][k] == '1':
					ans += 1
	print(ans)


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)


for t in range(int(input())):
	(r, c) = map(int, input().split())
	a = []
	for i in range(r):
		a.append(input())
	ans = 0
	for j in range(c):
		ct = 0
		for i in range(r):
			if a[i][j] == '1':
				ct += 1
		ans += ct * (ct - 1) // 2
	print(ans)


testcases = int(input())
while testcases > 0:
	testcases = testcases - 1
	(n, m) = map(int, input().split(' '))
	l = []
	for i in range(0, n):
		a = input()
		l.append(a)
	c = 0
	for j in range(0, m):
		x = []
		d = 0
		for i in range(0, n):
			x.append(l[i][j])
		for i in range(0, len(x)):
			if x[i] == '1':
				d = d + 1
		c = c + d * (d - 1) // 2
	print(c)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = [0] * m
	ans = 0
	for i in range(n):
		c = list(input())
		l = [int(i) + int(j) for (i, j) in zip(l, c)]
	for j in l:
		ans += j * (j - 1) // 2
	print(ans)


for item in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = []
	for j in range(n):
		b = int(input())
		a.append(b)
	res = 0
	for j in range(m):
		p = 0
		for k in range(n):
			rem = a[k] % 10
			a[k] = a[k] // 10
			if rem == 1:
				p = p + 1
		res = res + p * (p - 1) // 2
	print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		l = []
		s = input()
		for j in range(len(s)):
			l.append(int(s[j]))
		a.append(l)
	s = 0
	for i in range(m):
		x = 0
		for j in range(n):
			if a[j][i] == 1:
				x += 1
		s += x * (x - 1) // 2
	print(s)


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)


def nCr(n, r):
	return int(fact(n) / (fact(r) * fact(n - r)))

def fact(n):
	if n == 0:
		return 1
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = []
	for x in range(n):
		a.append(list(input()))
	count = 0
	for j in range(m):
		temp_count = 0
		for k in range(n):
			flag = a[k][j]
			if a[k][j] == '1':
				temp_count += 1
		count += nCr(temp_count, 2)
	print(count)


def fact(x):
	pro = 1
	for y in range(1, x + 1):
		pro = pro * y
	return pro
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	for j in range(n):
		a = list(input())
		p = []
		for k in range(m):
			p.append(int(a[k]))
		l.append(p)
	count = 0
	for j in range(m):
		s = 0
		for k in range(n):
			s = s + l[k][j]
		if s >= 2:
			count = count + int(fact(s) / (fact(s - 2) * 2))
	print(count)


def factorial(n):
	f = 1
	for i in range(1, n + 1):
		f *= i
	return f

def nCr(n, r):
	return int(factorial(n) / (factorial(n - r) * factorial(r)))
for t in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	A = []
	for i in range(N):
		A.append(list(input()))
	total_collision = 0
	for j in range(M):
		count = 0
		for i in range(N):
			count += int(A[i][j])
		if count == 1 or count == 0:
			collisions = 0
		else:
			collisions = nCr(count, 2)
		total_collision += collisions
	print(total_collision)


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


for _ in range(int(input())):
	(rows, columns) = map(int, input().split())
	l = [input() for _ in range(rows)]
	res = 0
	for i in range(columns):
		count = 0
		for j in range(rows):
			if l[j][i] == '1':
				count += 1
		res += count * (count - 1) // 2
	print(res)


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


total_testcases = int(input())
for testcase in range(total_testcases):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n):
		s = input()
		for j in range(len(s)):
			if s[j] == '1':
				d[j] = d.get(j, 0) + 1
	ans = 0
	for (key, value) in d.items():
		if value != 1:
			ans += value * (value - 1) // 2
	print(ans)


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


t = int(input())
while t:
	(n, m) = [int(i) for i in input().split()]
	mat = []
	for i in range(n):
		mat.append(input())
	ans = 0
	for i in range(m):
		cnt = 0
		for j in range(n):
			if mat[j][i] == '1':
				cnt += 1
		ans += cnt * (cnt - 1) // 2
	print(ans)
	t -= 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	k = []
	for q in range(n):
		l = list(input())
		k.append(l)
	c = 0
	for w in range(m):
		r = 0
		for e in range(n):
			r += int(k[e][w])
		g = r * (r - 1)
		c += g // 2
	print(c)