You are given N binary strings S_{1}, S_{2}, \dots, S_{N}, each of length M. You want to concatenate all the N strings in some order to form a single large string of length N \cdot M. Find the minimum possible number of inversions the resulting string can have.

A binary string is defined as a string consisting only of '0' and '1'.

An *inversion* in a binary string S is a pair of indices (i, j) such that i < j and S_{i} = '1', S_{j} = '0'. For example, the string S = "01010" contains 3 inversions : (2, 3), (2, 5), (4, 5).

Note that you are not allowed to change the order of characters within any of the strings S_{i} - you are only allowed to concatenate the strings themselves in whatever order you choose. For example, if you have "00" and "10" you can form "0010" and "1000", but not "0001".

------ Input Format ------ 

- The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N, M.
- N lines follow, the i^{th} of which contains the string S_{i} of length M.

------ Output Format ------ 

For each test case, print a single line containing one integer - the minimum possible number of inversions in the resulting string.

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$2 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$2 ≤ N \cdot M ≤ 2\cdot 10^{5}$
$\lvert S_{i} \rvert = M$
$S_{i}$ contains only characters '$0$' and '$1$'.
- Sum of $N \cdot M$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
4
2 1
0
1
3 2
10
00
01
2 4
0010
1011
3 4
1011
1101
0101

----- Sample Output 1 ------ 
0
2
3
11
----- explanation 1 ------ 
Test case $1$: Two strings can be formed : $S_{1} + S_{2} = $"$01$", $S_{2} + S_{1} $= "$10$". The first string does not have any inversion while the second has one inversion : $(1, 2)$.

Test case $2$:  Both $S_{2} + S_{1} + S_{3} = $"$001001$", $S_{2} + S_{3} + S_{1} = $"$000110$" contain $2$ inversions. It can be verified that no other order results in fewer inversions.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Data structures


Solutions:
def count(s):
	ones1 = 0
	for ele in s:
		if ele == '1':
			ones1 += 1
	return ones1
t = int(input())
while t > 0:
	sizes = input().split(' ')
	n = int(sizes[0])
	m = int(sizes[1])
	arr = [0] * n
	for i in range(0, n):
		st = input()
		arr[i] = st
	marr = []
	for item in arr:
		cnt = count(item)
		marr.append((cnt, item))
	marr.sort()
	res = ''
	for item in marr:
		res += item[1]
	tsize = n * m
	onecnt = 0
	inv = 0
	for i in range(0, tsize):
		if res[i] == '1':
			onecnt += 1
			continue
		else:
			inv += onecnt
	print(inv)
	t -= 1


from sys import stdin
t = int(stdin.readline().rstrip())
while t > 0:
	(n, m) = map(int, stdin.readline().rstrip().split(' '))
	nums = []
	for i in range(n):
		s = stdin.readline().strip()
		nums.append(s)
	nums.sort(key=lambda i: i.count('1'))
	nums = ''.join(nums)
	ones = 0
	inversions = 0
	for i in nums:
		if i == '1':
			ones += 1
		else:
			inversions += ones
	print(inversions)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	strings = []
	for _ in range(n):
		strings.append(input())
	strings = sorted(strings, key=lambda x: x.count('1'))
	string = ''.join(strings)[::-1]
	inversions = 0
	zero_count = 0
	for item in string:
		if item == '0':
			zero_count += 1
		else:
			inversions += zero_count
	print(inversions)


from collections import Counter
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	S = []
	for i in range(N):
		T = []
		t = input()
		C = dict(Counter(t))
		T.append(t)
		if '1' in C:
			T.append(C['1'])
		else:
			T.append(0)
		S.append(T)
	S.sort(key=lambda x: x[1])
	A = ''
	for i in S:
		A += i[0]
	ans = 0
	C = dict(Counter(A))
	Z = 0
	if '0' in C:
		Z += C['0']
	for i in range(len(A)):
		if A[i] == '1':
			ans += Z
		else:
			Z -= 1
	print(ans)


for _ in range(int(input())):
	(n, m) = (int(i) for i in input().split())
	a = []
	for i in range(n):
		s = input()
		a.append(s)
	a.sort(key=lambda i: i.count('1'))
	one = 0
	ans = 0
	for i in ''.join(a):
		if i == '1':
			one += 1
		else:
			ans += one
	print(ans)


def ff(x):
	su = 0
	z = 0
	for i in reversed(range(len(x))):
		if x[i] == '0':
			z += 1
		else:
			su += z
	return (len(x) - z, su)
t = int(input())
while t:
	t -= 1
	a = list(map(int, input().split()))
	ti = 0
	one = []
	for i in range(a[0]):
		x = input()
		(on, inv) = ff(x)
		ti += inv
		one.append(on)
	one.sort()
	su = 0
	for i in reversed(range(len(one))):
		su += one[i]
	for i in range(len(one)):
		ti += one[i] * ((len(one) - i - 1) * a[1] - (su - one[i]))
		su -= one[i]
	print(ti)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	list1 = [input() for x in range(n)]
	list1.sort(key=lambda a: a.count('1'))
	ans = ones = 0
	for i in ''.join(list1):
		if i == '1':
			ones += 1
		else:
			ans += ones
	print(ans)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	arr = ['' for i in range(n)]
	for i in range(n):
		arr[i] = input()
	arr.sort(key=lambda x: x.count('1'))
	st = ''.join(arr)
	cnt_z = 0
	cnt_o = 0
	for i in range(len(st) - 1, -1, -1):
		if st[i] == '0':
			cnt_z += 1
		else:
			cnt_o += cnt_z
	print(cnt_o)
	t -= 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	l = []
	for j in range(n):
		s = str(input())
		(c0, c1) = (0, 0)
		for k in range(m):
			if s[m - 1 - k] == '1':
				c += c0
				c1 += 1
			else:
				c0 += 1
		l.append(c0)
	l.sort(reverse=True)
	ss = sum(l)
	for j in range(n):
		c += (m - l[j]) * (ss - l[j])
		ss -= l[j]
	print(c)


def minInversion(string, m):
	string.sort(key=lambda x: x.count('1'))
	res = ''.join(string)
	zeroCounter = 0
	ans = 0
	for x in reversed(res):
		if x == '0':
			zeroCounter += 1
		else:
			ans += zeroCounter
	return ans
for i in range(int(input())):
	(n, m) = map(int, input().split())
	string = [input().strip() for i in range(n)]
	print(minInversion(string, m))


def solve(N, M, A):
	A.sort(key=lambda x: x.count('1'))
	a = ''.join(A)
	ans = 0
	zero = 0
	for x in reversed(a):
		if x == '0':
			zero += 1
		else:
			ans += zero
	return ans
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	A = []
	for _ in range(N):
		A.append(input().strip())
	print(solve(N, M, A))


def numberOfInversions(s: str, l: int) -> int:
	ans = 0
	num_ones = 0
	for i in range(l):
		if s[i] == '1':
			num_ones += 1
		else:
			ans += num_ones
	return ans
t = int(input().strip())
result = []
for _ in range(t):
	(n, m) = list(map(int, input().rstrip().split()))
	arr = [input().strip() for i in range(n)]
	arr.sort(key=lambda s: s.count('1'))
	ans_str = ''.join(arr)
	result.append(numberOfInversions(ans_str, n * m))
for r in result:
	print(r)


def sortkey(a):
	return a[1]

def inversion(string):
	left1s = 0
	count = 0
	for ele in string:
		if ele == '1':
			left1s += 1
		else:
			count += left1s
	return count
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	while n != 0:
		s = input()
		count = 0
		for ele in s:
			if ele == '0':
				count += 1
		a.append([s, count])
		n -= 1
	a.sort(key=sortkey, reverse=True)
	string = ''
	for val in a:
		string += val[0]
	res = inversion(string)
	print(res)


def mergeSort(arr, n):
	temp_arr = [0] * n
	return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
	inv_count = 0
	if left < right:
		mid = (left + right) // 2
		inv_count += _mergeSort(arr, temp_arr, left, mid)
		inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
		inv_count += merge(arr, temp_arr, left, mid, right)
	return inv_count

def merge(arr, temp_arr, left, mid, right):
	i = left
	j = mid + 1
	k = left
	inv_count = 0
	while i <= mid and j <= right:
		if arr[i] <= arr[j]:
			temp_arr[k] = arr[i]
			k += 1
			i += 1
		else:
			temp_arr[k] = arr[j]
			inv_count += mid - i + 1
			k += 1
			j += 1
	while i <= mid:
		temp_arr[k] = arr[i]
		k += 1
		i += 1
	while j <= right:
		temp_arr[k] = arr[j]
		k += 1
		j += 1
	for loop_var in range(left, right + 1):
		arr[loop_var] = temp_arr[loop_var]
	return inv_count
t = int(input())
while t > 0:
	nm = list(map(int, input().strip().split()))
	(n, m) = (nm[0], nm[1])
	li = []
	while n > 0:
		s = input()
		li.append(s)
		n -= 1
	li1 = sorted(li, key=lambda x: x.count('1'))
	li2 = []
	for i in li1:
		j = list(i)
		li2.extend(j)
	li3 = list(map(int, li2))
	ans = mergeSort(li3, len(li3))
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for i in range(n)]
	a.sort(key=lambda i: i.count('1'))
	inver = ones = 0
	for i in ''.join(a):
		if i == '1':
			ones += 1
		if i == '0':
			inver += ones
	print(inver)


def king_coding():
	(n, m) = map(int, input().split())
	L = []
	for i in range(n):
		L.append(input())
	L.sort(key=lambda b: b.count('1'))
	(c, s) = (0, 0)
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if L[n - i][m - j] == '0':
				c += 1
			else:
				s += c
	print(s)
for _ in range(int(input())):
	king_coding()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for i in range(n)]
	a.sort(key=lambda s: s.count('1'))
	new_s = ''.join(a)
	ones = inv = 0
	for i in new_s:
		if i == '1':
			ones += 1
		else:
			inv += ones
	print(inv)


def inver(st):
	cnt_one = 0
	ans = 0
	for ch in st:
		if ch == '1':
			cnt_one += 1
		else:
			ans += cnt_one
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [input() for _ in range(n)]
	l.sort(key=lambda s: s.count('1'))
	bigstr = ''.join(l)
	print(inver(bigstr))


import sys
input = sys.stdin.readline
from functools import lru_cache

@lru_cache(None)
def GetNumInversions(string):
	num_ones_to_the_left = [0]
	for x in string[:-1]:
		if x == '1':
			num_ones_to_the_left += [num_ones_to_the_left[-1] + 1]
		else:
			num_ones_to_the_left += [num_ones_to_the_left[-1]]
	num_inversions = 0
	for (x, num_ones) in zip(string, num_ones_to_the_left):
		if x == '0':
			num_inversions += num_ones
	return num_inversions
num_test_cases = int(input())
for _ in range(num_test_cases):
	(num_strings, string_length) = [int(x) for x in input().split()]
	strings = [input().strip() for i in range(num_strings)]
	strings.sort(key=lambda x: (x.count('1'), GetNumInversions(x)))
	concat_string = ''.join(strings)
	print(GetNumInversions(concat_string))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	b = [input() for i in range(n)]
	b.sort(key=lambda x: x.count('1'))
	inversion = 0
	cnt = 0
	for i in ''.join(b):
		if i == '1':
			cnt += 1
		else:
			inversion = inversion + cnt
	print(inversion)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		r = input()
		l.append(r)
	l.sort(key=lambda x: x.count('1'))
	s = ''
	for i in range(len(l)):
		s = s + l[i]
	d = []
	s = list((char for char in s))
	for i in range(len(s)):
		if s[i] == '0':
			d.append(i)
	su = 0
	for i in range(0, len(d)):
		if i == 0:
			su = su + d[0] * len(d)
		else:
			su = su + (d[i] - d[i - 1] - 1) * (len(d) - i)
	print(su)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = [input().strip('\r') for i in range(n)]
	l.sort(key=lambda x: x.count('1'))
	c = d = 0
	for x in ''.join(l):
		if x == '1':
			c += 1
		else:
			d += c
	print(d)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = []
	for el in range(n):
		ans.append(input())
	ans.sort(key=lambda x: x.count('1'))
	res = ''
	for ch in ans:
		res += ch
	ans = 0
	odd = 0
	for ch in res:
		if ch == '1':
			odd += 1
		else:
			ans += odd
	print(ans)


def check_inv(word):
	ones = 0
	invs = 0
	for i in word:
		if i == '1':
			ones += 1
		else:
			invs += ones
	return invs
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	words = sorted([input().strip() for i in range(n)], key=lambda x: x.count('1'))
	print(check_inv(''.join(words)))


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	l = []
	for i in range(m):
		s = input()
		l.append(s)
	l.sort(key=lambda f: f.count('1'))
	a = 0
	l = ''.join(l)
	z = l.count('0')
	for i in range(len(l)):
		if l[i] == '1':
			a += z
		else:
			z -= 1
	print(a)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	A = [0] * n
	for i in range(n):
		A[i] = input()
	A.sort(key=lambda i: i.count('1'))
	(ones, count) = (0, 0)
	for i in ''.join(A):
		if i == '1':
			ones += 1
		else:
			count += ones
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	res = []
	for i in range(n):
		k = input()
		res.append([k.count('0'), k])
	res.sort(key=lambda x: x[0], reverse=True)
	t = ''
	for i in res:
		t += i[1]
	m = t.count('0')
	ans = 0
	for i in t:
		if i == '0':
			m -= 1
		else:
			ans += m
	print(ans)


for _ in range(int(input())):
	l = []
	(x, y) = map(int, input().split())
	for i in range(x):
		s = str(input())
		l.append(s)
	l.sort(key=lambda x: x.count('1'))
	ans = 0
	c = 0
	s = str('')
	for i in range(x):
		s += l[i]
	for i in range(len(s)):
		if s[i] == str(1):
			c += 1
		elif s[i] == str(0):
			ans += c
	print(ans)


for _ in range(int(input())):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	strings = list()
	for _ in range(N):
		strings.append(input())
	strings = sorted(strings, key=lambda s: s.count('1'))
	ones = 0
	inv = 0
	for c in ''.join(strings):
		if c == '1':
			ones += 1
		else:
			inv += ones
	print(inv)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	l.sort(key=lambda b: b.count('1'))
	p = ''
	for i in l:
		p = p + i
	z = 0
	ans = 0
	for i in range(len(p) - 1, -1, -1):
		if p[i] == '0':
			z = z + 1
		elif p[i] == '1':
			ans = ans + z
	print(ans)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	ones = 0
	res = 0
	s = [input() for i in range(n)]
	s.sort(key=lambda x: x.count('1'))
	for i in ''.join(s):
		if i == '1':
			ones += 1
		else:
			res += ones
	print(res)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	b = [input() for i in range(n)]
	b.sort(key=lambda i: i.count('1'))
	o = i = 0
	for j in ''.join(b):
		if j == '1':
			o += 1
		else:
			i += o
	print(i)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	L = []
	for j in range(n):
		s = input()
		o = s.count('1')
		l.append([o, j])
		L.append(s)
	l.sort()
	p = []
	for k in range(len(l)):
		v = l[k]
		d = v[1]
		p.append(L[d])
	v = ''.join(map(str, p))
	a = v.count('0')
	b = m * n - a
	c = 0
	for j in range(len(v)):
		if v[j] == '0':
			a -= 1
		else:
			c += a
	print(c)


tc = int(input())
for _ in range(tc):
	(c, bitc) = map(int, input().split())
	map_ = {}
	for i in range(c):
		t = input()
		tc = t.count('1')
		if tc not in map_:
			map_[tc] = []
		map_[tc].append(t)
	keys = sorted(map_.keys(), reverse=True)
	for key in map_:
		map_[key].sort(key=lambda x: int(x, 2))
	text = ''
	for key in keys:
		text = ''.join(map_[key]) + text
	text = text[::-1]
	zc = 0
	res = 0
	for c in text:
		if c == '0':
			zc += 1
		else:
			res += zc
	print(res)


def countinverse(no):
	count = 0
	val = 0
	for x in reversed(no):
		if x == '0':
			val += 1
		if x == '1':
			count += val
	return count
for _ in range(int(input())):
	arr = []
	(string, length) = map(int, input().split())
	for s in range(string):
		arr.append(input())
	arr.sort(key=lambda x: x.count('1'))
	arr = map(str, arr)
	no = ''.join(arr)
	print(countinverse(no))


def inversion(string):
	(ones, count) = (0, 0)
	for i in string:
		if i == '1':
			ones += 1
		else:
			count += ones
	print(count)
for i in range(int(input())):
	(N, M) = map(int, input().split(' '))
	bin = []
	for s in range(N):
		K = input()
		bin.append(K)
	bin.sort(key=lambda val: val.count('1'))
	string = ''.join(bin)
	inversion(string)


def func(x):
	ones = 0
	for ch in x:
		if ch == '1':
			ones += 1
	return ones
t = int(input())
for T in range(t):
	(n, m) = map(int, input().split())
	strings = []
	for i in range(n):
		strings.append(input())
	strings = sorted(strings, key=func)
	concat_str = ''.join(strings)
	ones = 0
	ans = 0
	for ch in concat_str:
		if ch == '0':
			ans += ones
		else:
			ones += 1
	print(ans)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		s = input()
		l.append(s)
	l.sort(key=lambda x: x.count('1'))
	s = ''.join(l)
	(ones, c) = (0, 0)
	for i in s:
		if i == '1':
			ones += 1
		else:
			c += ones
	print(c)


T = int(input())
for j in range(1, T + 1):
	(n, m) = map(int, input().split())
	a = [input() for i in range(n)]
	a.sort(key=lambda x: x.count('1'))
	invs = one = 0
	for i in ''.join(a):
		if i == '1':
			one += 1
		else:
			invs += one
	print(invs)


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [input() for x in range(n)]
	arr.sort(key=lambda i: i.count('1'))
	ones = invs = 0
	for i in ''.join(arr):
		if i == '1':
			ones += 1
		else:
			invs += ones
	print(invs)


from collections import Counter
import bisect as bs
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	a = [0] * n
	for i in range(n):
		s = input().strip()
		a[i] = s
		d[i] = s.count('0')
	d = dict(sorted(d.items(), key=lambda item: item[1], reverse=True))
	s = ''
	for each in d:
		s += a[each]
	ans = 0
	x = 0
	for each in s:
		if each == '1':
			x += 1
		else:
			ans += x
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		s = input()
		count1 = 0
		count0 = 0
		for i in s:
			if i == '1':
				count1 += 1
			else:
				count0 += 1
		l.append((count1, s))
	l.sort()
	a = ''
	b = 0
	for (i, j) in l:
		a += j
	count = 0
	for i in a:
		if i == '1':
			count += 1
		else:
			b += count
	print(b)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [input() for i in range(n)]
	arr.sort(key=lambda i: i.count('1'))
	count1 = 0
	inv = 0
	for i in ''.join(arr):
		if i == '1':
			count1 += 1
		else:
			inv += count1
	print(inv)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l1 = [input() for i in range(n)]
	l1.sort(key=lambda i: i.count('1'))
	one = ans = 0
	for i in ''.join(l1):
		if i == '1':
			one += 1
		else:
			ans += one
	print(ans)


def count_inv(string):
	ones = ans = 0
	for i in string:
		if i == '1':
			ones += 1
		else:
			ans += ones
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		arr.append(input())
	arr.sort(key=lambda x: x.count('1'))
	arr = ''.join(arr)
	print(count_inv(arr))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	arr = []
	for i in range(a):
		arr.append(input())
	arr.sort(key=lambda x: x.count('1'))
	c1 = 0
	res = 0
	for i in arr:
		for j in i:
			if j == '1':
				c1 += 1
			else:
				res += c1
	print(res)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	l.sort(key=lambda x: x.count('1'))
	ans = ''
	for i in l:
		ans += i
	o = 0
	res = 0
	for i in range(len(ans)):
		if ans[i] == '1':
			o += 1
		else:
			res += o
	print(res)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = ''
	a = []
	for i in range(n):
		x = input()
		c = x.count('1')
		a.append([c, x])
	a.sort()
	for i in range(n):
		s = s + a[i][1]
	z = 0
	ans = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '0':
			z = z + 1
		else:
			ans = ans + z
	print(ans)


class String:

	def __init__(self, a=None, b=0):
		self.s = a
		self.ones = 0

	def calculate(self):
		for i in self.s:
			if i == '1':
				self.ones = self.ones + 1

	def __lt__(self, other):
		if self.ones < other.ones:
			return True
		elif self.ones > other.ones:
			return False
		elif self.s < other.s:
			return True
		else:
			return False
T = int(input())
for _ in range(0, T):
	objects = []
	(N, M) = map(int, input().split())
	for i in range(0, N):
		objects.append(String())
		objects[i].s = input()
		objects[i].calculate()
	sorted_objects = sorted(objects)
	string = ''
	for i in sorted_objects:
		string = string + i.s
	ones_count = 0
	inversions = 0
	for i in string:
		if i == '1':
			ones_count = ones_count + 1
		else:
			inversions = inversions + ones_count
	print(inversions)


t = int(input())

def comp(x):
	count1 = 0
	for i in x:
		if i == '1':
			count1 += 1
	return count1
while t > 0:
	t -= 1
	(n, m) = list(map(int, input().split(' ')))
	nums = list()
	while n > 0:
		n -= 1
		t1 = str(input())
		nums.append(t1)
	nums.sort(key=lambda x: comp(x))
	a = ''.join(nums)
	inversion_count = 0
	one_count = 0
	for i in a:
		if i == '1':
			one_count += 1
		else:
			inversion_count += one_count
	print(inversion_count)


test = int(input())
for i in range(0, test):
	(n, v) = map(int, input().split())
	list1 = []
	list2 = []
	for z in range(n):
		b = input()
		list1.append(b)
	list1.sort(key=lambda i: i.count('1'))
	ans = ''
	for p in range(n):
		ans = ans + list1[p]
	one = 0
	cost = 0
	for f in range(0, len(ans)):
		if ans[f] == '1':
			one += 1
		else:
			cost += one
	print(cost)


import sys, numpy as np

def solve(test):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		x = input().strip()
		arr.append(x)
	count1 = []
	for i in range(len(arr)):
		count1.append([arr[i], arr[i].count('1')])
	count1 = sorted(count1, key=lambda x: x[1])
	ans = []
	for i in range(len(count1)):
		ans.append(count1[i][0])
	temp = ''.join(ans)
	answer = 0
	count = 0
	for i in temp[::-1]:
		if i == '0':
			count += 1
		else:
			answer += count
	print(answer)
test_case = int(input())
for test in range(test_case):
	solve(test + 1)


def func(N, M, arr):
	i = 0
	dp = [[] for i in range(N)]
	d = {}
	for i in range(N):
		c = 0
		for j in arr[i]:
			if j == '1':
				c += 1
		d[i] = c
	d = dict(sorted(d.items(), key=lambda x: x[1]))
	pos = 0
	for (i, j) in d.items():
		dp[pos] = arr[i]
		pos += 1
	ans = 0
	s = ''
	inver = 0
	for i in dp:
		for j in range(M):
			if i[j] == '1':
				ans += 1
			else:
				inver += ans
	return inver
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	arr = []
	for j in range(N):
		x = list(input())
		arr.append(x)
	print(func(N, M, arr))


import math
import random as rd
import bisect
import collections

def combination(n, r):
	return math.comb(n, r)

def listing():
	return list(map(int, input().split()))

def intp():
	return int(input())

def inp():
	return input()

def inpspl():
	return input().split()

def mapping():
	return map(int, input().split())

def sqrt(n):
	return math.sqrt(n)

def gcd(a, b):
	return math.gcd(a, b)

def lcm(a, b):
	return a * b // gcd(a, b)

def p(s):
	print(s)

def lsetl(lst):
	return list(set(lst))

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(abs(n - r))

def frequencyofall(lst):
	return dict(collections.Counter(lst))

def ispowerof2(n):
	return n & n - 1 == 0

def ispowerof3(n):
	return math.log10(n) / math.log10(3) % 1 == 0

def dictionarysort(d):
	return collections.OrderedDict(sorted(d.items()))

def bintoint(s):
	return int(s, 2)

def solve():
	for _ in range(intp()):
		(n, m) = mapping()
		l = []
		for __ in range(n):
			s = inp()
			l.append([s.count('1'), s])
		l.sort()
		st = ''
		for i in l:
			st += i[1]
		o = 0
		ans = 0
		for i in range(len(st)):
			if st[i] == '1':
				o += 1
			else:
				ans += o
		print(ans)
solve()


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	S = []
	for i in range(m):
		s = input()
		S.append(s)
	S = [(int(s, 2), s, i) for (i, s) in enumerate(S)]
	S.sort(key=lambda x: x[1].count('1'))
	s_joined = ''.join((s for (v, s, i) in S))
	pref_s = [0]
	ans = 0
	for i in range(len(s_joined) - 1, -1, -1):
		if s_joined[i] == '0':
			pref_s.append(pref_s[-1] + 1)
		else:
			pref_s.append(pref_s[-1])
	pref_s.pop(0)
	pref_s.reverse()
	for i in range(len(s_joined)):
		if s_joined[i] == '1':
			ans += pref_s[i]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	l1 = []
	inv = 0
	for i in range(n):
		st = input()
		l.append(st)
		co = 0
		for j in range(m):
			if st[j] == '1':
				co = co + 1
			else:
				inv = inv + co
		l1.append(co)
	l1.sort()
	prev1 = 0
	for i in range(1, n):
		prev1 = prev1 + l1[i - 1]
		inv = inv + (m - l1[i]) * prev1
	print(inv)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			print(p)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [input() for i in range(n)]
	a.sort(key=lambda x: x.count('1'))
	one = 0
	inv = 0
	for i in ''.join(a):
		if i == '1':
			one += 1
		else:
			inv += one
	print(inv)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = []
	for i in range(n):
		s = input()
		c = s.count('1')
		li.append([c, s])
	li.sort()
	k = ''
	for i in range(n):
		k = k + li[i][1]
	ans = 0
	j = 0
	for i in range(n * m):
		if k[i] == '0':
			ans = ans + j
		else:
			j = j + 1
	print(ans)


from os import environ
import sys
import math
from bisect import bisect, bisect_left, insort
if environ.get('epoweripi'):
	sys.stdin = open('../../input.txt', 'r')
	sys.stdout = open('../../output.txt', 'w')

	def debug(z=''):
		print(str(z) + '\n')
else:

	def debug(z=''):
		return
input = sys.stdin.readline
print = sys.stdout.write
mod = 10 ** 9 + 7

def I():
	return input().strip()

def II():
	return int(input().strip())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def P(z=''):
	print(str(z) + '\n')

def PSPACE(z=''):
	print(str(z) + ' ')

def LP(z=[]):
	for i in z:
		print(str(i) + ' ')
	print('\n')

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)

def sieve(n):
	isPrimes = [True for i in range(n + 1)]
	(isPrimes[0], isPrimes[1]) = (False, False)
	p = 2
	while p * p <= n:
		if isPrimes[p] == True:
			for j in range(p * p, n + 1, p):
				isPrimes[j] = False
		p += 1

def swap(arr, i, j):
	(arr[i], arr[j]) = (arr[j], arr[i])
for _ in range(II()):
	(n, m) = MI()
	l = ['' for x in range(n)]
	for i in range(n):
		l[i] = I()

	def func(x):
		one_count = 0
		for i in x:
			if i == '1':
				one_count += 1
		return one_count
	l.sort(key=lambda x: func(x))
	newl = ['' for x in range(n * m)]
	k = 0
	for i in range(n):
		for j in range(m):
			newl[k] = l[i][j]
			k += 1
	news = ''.join(newl)
	zero_count = [0 for x in range(n * m)]
	s = 0
	for i in reversed(range(n * m)):
		if news[i] == '0':
			s += 1
		zero_count[i] = s
	count1 = 0
	for i in range(n * m - 1):
		if news[i] == '1':
			count1 += zero_count[i + 1]
	P(count1)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = []
	for i in range(N):
		k = input()
		A.append(k)
	A.sort(key=lambda x: x.count('1'))
	ans = ''.join(A)
	z = ans.count('0')
	c = 0
	for i in range(len(ans)):
		if ans[i] == '0':
			z -= 1
		else:
			c += z
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(input())
	l.sort(key=lambda x: x.count('1'))
	s = ''
	for i in l:
		s += i
	ones = 0
	ans = 0
	for i in s:
		if i == '0':
			ans += ones
		else:
			ones += 1
	print(ans)


def cont(ele):
	flag = 0
	for i in ele:
		if i == '0':
			flag += 1
	return flag
t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	zer = []
	one = []
	zersum = [0] * n
	u = 0
	for nn in range(n):
		ele = input()
		r = cont(ele)
		zer.append(r)
		c = r
		for y in ele:
			if y == '1':
				u += c
			else:
				c -= 1
	zer.sort(reverse=True)
	p = 0
	for el in zer:
		one.append(m - el)
	for w in range(n - 1, -1, -1):
		zersum[w] = p + zer[w]
		p = zersum[w]
	for y in range(n - 1):
		u += one[y] * zersum[y + 1]
	print(u)


def solve():
	(n, m) = map(int, input().split())
	a = [input() for i in range(n)]
	a.sort(key=lambda i: i.count('1'))
	ones = invs = 0
	for i in ''.join(a):
		if i == '1':
			ones += 1
		else:
			invs += ones
	print(invs)
for _ in range(int(input())):
	solve()


try:
	from debugger import debug
except ImportError:

	def debug(**kwargs):
		pass
	pass

def solve():
	(n, m) = map(int, input().split())
	a = [input() for i in range(n)]
	a.sort(key=lambda i: i.count('1'))
	ones = invs = 0
	for i in ''.join(a):
		if i == '1':
			ones += 1
		else:
			invs += ones
	print(invs)
for _ in range(int(input())):
	solve()


def process(List):
	(Min, one) = (0, 0)
	List.sort(key=lambda item: item.count('1'))
	val = ''.join(List)
	for i in val:
		if i == '0':
			Min += one
		if i == '1':
			one += 1
	return Min
for _ in range(int(input())):
	List = []
	(N, M) = map(int, input().split())
	count = 0
	for i in range(N):
		List.append(input())
	print(process(List))


def check(a):
	return a.count('1')
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	data = [input() for i in range(n)]
	data.sort(key=lambda x: x.count('1'))
	s = ''
	s = s.join(data)
	total = s.count('0')
	sharma = 0
	for i in s:
		if i == '0':
			total -= 1
		else:
			sharma += total
	print(sharma)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		s = input()
		arr.append(s)
	arr = sorted(arr, key=lambda x: x.count('1'))
	string = ''.join(arr)
	leni = len(string)
	ans = 0
	ones = 0
	for i in range(leni):
		if string[i] == '1':
			ones += 1
		else:
			ans += ones
	print(ans)


def count(x):
	ans = 0
	for i in x:
		if i == '1':
			ans += 1
	return ans

def mgc(n, a):
	a.sort()
	x = ''
	for i in a:
		x += i[1]
	ans = 0
	zeroes = 0
	for i in x:
		if i == '0':
			zeroes += 1
	for i in range(len(x)):
		if x[i] == '1':
			ans += zeroes
		else:
			zeroes -= 1
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		temp = input()
		arr.append([count(temp), temp])
	print(mgc(n, arr))


def solve():
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		s = input()
		l.append((s, s.count('0')))
	l = sorted(l, key=lambda x: x[1], reverse=True)
	ans = ''
	for i in l:
		ans += i[0]
	count_0 = 0
	answer = 0
	for i in ans[::-1]:
		if i == '1':
			answer += count_0
		else:
			count_0 += 1
	print(answer)
t = int(input())
while t != 0:
	solve()
	t -= 1