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.

见题面

见题面