You are given a picture consisting of $n$ rows and $m$ columns. Rows are numbered from $1$ to $n$ from the top to the bottom, columns are numbered from $1$ to $m$ from the left to the right. Each cell is painted either black or white. 

You think that this picture is not interesting enough. You consider a picture to be interesting if there is at least one cross in it. A cross is represented by a pair of numbers $x$ and $y$, where $1 \le x \le n$ and $1 \le y \le m$, such that all cells in row $x$ and all cells in column $y$ are painted black.

For examples, each of these pictures contain crosses:

 [Image] 

The fourth picture contains 4 crosses: at $(1, 3)$, $(1, 5)$, $(3, 3)$ and $(3, 5)$.

Following images don't contain crosses:

 [Image] 

You have a brush and a can of black paint, so you can make this picture interesting. Each minute you may choose a white cell and paint it black.

What is the minimum number of minutes you have to spend so the resulting picture contains at least one cross?

You are also asked to answer multiple independent queries.


-----Input-----

The first line contains an integer $q$ ($1 \le q \le 5 \cdot 10^4$) — the number of queries.

The first line of each query contains two integers $n$ and $m$ ($1 \le n, m \le 5 \cdot 10^4$, $n \cdot m \le 4 \cdot 10^5$) — the number of rows and the number of columns in the picture.

Each of the next $n$ lines contains $m$ characters — '.' if the cell is painted white and '*' if the cell is painted black.

It is guaranteed that $\sum n \le 5 \cdot 10^4$ and $\sum n \cdot m \le 4 \cdot 10^5$.


-----Output-----

Print $q$ lines, the $i$-th line should contain a single integer — the answer to the $i$-th query, which is the minimum number of minutes you have to spend so the resulting picture contains at least one cross.


-----Example-----
Input
9
5 5
..*..
..*..
*****
..*..
..*..
3 4
****
.*..
.*..
4 3
***
*..
*..
*..
5 5
*****
*.*.*
*****
..*.*
..***
1 4
****
5 5
.....
..*..
.***.
..*..
.....
5 3
...
.*.
.*.
***
.*.
3 3
.*.
*.*
.*.
4 4
*.**
....
*.**
*.**

Output
0
0
0
0
0
4
1
1
2



-----Note-----

The example contains all the pictures from above in the same order.

The first 5 pictures already contain a cross, thus you don't have to paint anything.

You can paint $(1, 3)$, $(3, 1)$, $(5, 3)$ and $(3, 5)$ on the $6$-th picture to get a cross in $(3, 3)$. That'll take you $4$ minutes.

You can paint $(1, 2)$ on the $7$-th picture to get a cross in $(4, 2)$.

You can paint $(2, 2)$ on the $8$-th picture to get a cross in $(2, 2)$. You can, for example, paint $(1, 3)$, $(3, 1)$ and $(3, 3)$ to get a cross in $(3, 3)$ but that will take you $3$ minutes instead of $1$.

There are 9 possible crosses you can get in minimum time on the $9$-th picture. One of them is in $(1, 1)$: paint $(1, 2)$ and $(2, 1)$.

Difficulty: interview

Starter code:

Solutions:
import sys

q = int(sys.stdin.readline().strip())
for t in range(0, q):
    n, m = list(map(int, sys.stdin.readline().strip().split()))
    L = []
    R = [0] * n
    C = [0] * m
    for i in range (0, n):
        L.append(sys.stdin.readline().strip())
        for j in range (0, m):
            if L[i][j] != "*":
                R[i] = R[i] + 1
                C[j] = C[j] + 1
    ans = n + m - 1
    for i in range (0, n):
        for j in range (0, m):
            x = 0
            if L[i][j] != "*":
                x = -1
            ans = min([ans, R[i]+C[j]+x])
    print(ans)

import sys
Q = int(input())
for _ in range(Q):
    N, M = map(int, sys.stdin.readline().split())
    G = [[1 if s == '*' else 0 for s in sys.stdin.readline().strip()] for _ in range(N)]
    ans = 10**9+7
    G1 = [sum(g) for g in G]
    G = list(map(list, zip(*G)))
    G2 = [sum(g) for g in G]
    G = list(map(list, zip(*G)))
    K = N + M - 1
    for i in range(N):
        for j in range(M):
            if G[i][j]:
                ans = min(ans, K - (G1[i] + G2[j] - 1))
            else:
                ans = min(ans, K - (G1[i] + G2[j]))
    sys.stdout.write('{}\n'.format(ans))

import sys
import math
input = sys.stdin.readline

q=int(input())
for i in range(q):
	n,m=list(map(int,input().split()))
	r=[0]*n
	c=[0]*m
	arr=[]
	for i in range(n):
		arr.append(input())

	for i in range(n):
		for j in range(m):
			if arr[i][j]==".":
				r[i]+=1
				c[j]+=1
	minn=1000000000
	for i in range(n):
		for j in range(m):
			if arr[i][j]==".":
				minn=min(minn,r[i]+c[j]-1)
			else:
				minn=min(minn,r[i]+c[j])

	print(minn)
		


q = int(input())
for query in range(q):
	n, m = list(map(int, input().split()))
	matrix = [input() for i in range(n)]
	row = [0] * n
	col = [0] * m
	for i in range(n):
		suma = 0
		for j in range(m):
			if matrix[i][j] == '*':
				suma += 1
		row[i] = suma
	for j in range(m):
		suma = 0
		for i in range(n):
			if matrix[i][j] == '*':
				suma += 1
		col[j] = suma
	wynik = 100000000000
	for i in range(n):
		for j in range(m):
			pom = m + n - 1 - (row[i] + col[j] - (1 if matrix[i][j] == '*' else 0))
			wynik = min(wynik, pom)
	print(wynik)
			


from sys import stdin
c=int(stdin.readline().strip())
for i in range(c):
    n,m=list(map(int,stdin.readline().strip().split()))
    s=[stdin.readline().strip() for j in range(n)]
    ms=[]
    ns=[]
    for j in range(n):
        ns.append(s[j].count("."))
    
    for j in range(m):
        ms.append(0)
        for k in range(n):
            if s[k][j]==".":
                ms[-1]+=1
    ans=10**15
    for j in range(n):
        for k in range(m):
            x=ns[j]+ms[k]
            if s[j][k]==".":
                x-=1
            ans=min(ans,x)
    print(ans)


t = int(input())
for i in range(t):
    e,s = list(map(int, input().split()))
    f = []
    for h in range(e):
        f.append(input())
    now = 0
    mi = 0
    mi2 = []
    g = []
    for y in range(e):
        now = 0
        g = []
        for x in range(s):
            if(f[y][x]=="*"):
                now+=1
            else:
                g.append(x)
        if(now>mi):
            mi = now
            mi2 = []
            for k in range(len(g)):
                mi2.append(g[k])
        elif(now==mi):
            for k in range(len(g)):
                mi2.append(g[k])
    now = 0
    ma = 0
    d = True
    for y in range(s):
        now = 0
        for x in range(e):
            if(f[x][y]=="*"):
                now+=1
        if(now>ma):
            ma = now
            if(y in mi2):
                d = False
            else:
                d = True
        elif(now==ma):
            if(y in mi2):
                d = False
    if(d):
        print(e-mi+s-ma)
    else:
        print(e-mi+s-ma-1)


import sys
input = sys.stdin.readline

Q=int(input())
for testcases in range(Q):
    n,m=list(map(int,input().split()))

    MAP=[list(input().strip()) for i in range(n)]

    R=[MAP[i].count("*") for i in range(n)]
    C=[]
    
    for j in range(m):
        M=[MAP[i][j] for i in range(n)]
        C.append(M.count("*"))

    ANS=float("inf")

    for i in range(n):
        for j in range(m):
            if MAP[i][j]=="*":
                ANS=min(ANS,n+m-R[i]-C[j])
            else:
                ANS=min(ANS,n+m-R[i]-C[j]-1)

    print(ANS)
                
    


n=int(input())
for i in range(n):
    x,y=list(map(int,input().split()))
    stolb=[0]*y
    stroki=[0]*x
    al=[]
    for j in range(x):
        st=input()
        al.append(st)
        for j2 in range(y):
            if st[j2]=='.':
                stroki[j]+=1
                stolb[j2]+=1
    mi=1000000000000000
    for j in range(x):
        for j2 in range(y):
            if al[j][j2]=='.':
                if stroki[j]+stolb[j2]-1<mi:
                    mi=stroki[j]+stolb[j2]-1
            else:
                if stroki[j]+stolb[j2]<mi:
                    mi=stroki[j]+stolb[j2]
    print(mi)


q = int(input())
for _ in range(q):
    n, m = list(map(int, input().split()))
    d = [list(input()) for _ in range(n)]
    count_x = list([x.count('*') for x in d])
    count_y = list([x.count('*') for x in zip(*d)])
    #dt = map(list, zip(*d))
    rls = n+m-1
    for i in range(n):
        for j in range(m):
            a = count_x[i]
            b = count_y[j]
            if d[i][j] == '*':
                rls = min(rls, n+m-a-b)
            else:
                rls = min(rls, n+m-a-b-1)
    print(rls)


import io, sys, atexit, os
import math as ma
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations


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


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


def nu ():
	return int (input ())


def find_gcd ( x, y ):
	while (y):
		x, y = y, x % y
	return x


def lcm ( x, y ):
	gg = find_gcd (x, y)
	return (x * y // gg)


mm = 1000000007
yp = 0


def solve ():
	t =nu()
	for tt in range (t):
		n,m=num()
		a=[0]*n
		x=[0]*n
		y=[0]*m
		for i in range(n):
			p=input()
			a[i]=[0]*m
			for j in range(m):
				if(p[j]=="*"):
					a[i][j]=1
			x[i]=sum(a[i])
		for i in range(m):
			cc=0
			for j in range(n):
				cc+=a[j][i]
			y[i]=cc
		mn=9999999999
		for i in range(n):
			for j in range(m):
				pp=0
				pp = (n - x [ i ]) + (m - y [ j ])
				if(a[i][j]==0):
					pp-=1
				mn=min(mn,pp)
		print(mn)





def __starting_point():
	solve ()
__starting_point()

from fractions import gcd
import math


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    q = int(input())
    for i in range(q):
        n,m = list(map(int, input().split()))
        a = [input() for i in range(n)]
        h = 0
        h_a = []
        for i in range(m):
            tmp = 0
            for j in range(n):
                if a[j][i] == '*':
                    tmp += 1
            if h < tmp:
                h = tmp
                h_a = [i]
            if h == tmp:
                h_a.append(i)
        w = 0
        w_a = []
        for i in range(n):
            tmp = len([i for i in a[i] if i == '*'])
            if w < tmp:
                w = tmp
                w_a = [i]
            if w == tmp:
                w_a.append(i)
        flag = 0
        for i in h_a:
            for j in w_a:
                if a[j][i] == '.':
                    flag = 1
                    break
        print(n+m-h-w-flag)

main()



for _ in range(int(input())):
    m,n=list(map(int,input().strip().split(' ')))
    grid=[]
    for i in range(m):
        grid+=[input()]
    row=[]
    col=[]
    MIN_row=10**10
    MIN_col=10**10
    for i in range(m):
        count=0
        for j in range(n):
            if grid[i][j]==".":
                count+=1
        row+=[count]
        MIN_row=min(MIN_row,count)
    for j in range(n):
        count=0
        for i in range(m):
            if grid[i][j]==".":
                count+=1
        col+=[count]
        MIN_col=min(MIN_col,count)
    
    want_row=set([])
    for i in range(len(row)):
        if row[i]==MIN_row:
            want_row.add(i)
            
    want_col=set([])
    for i in range(len(col)):
        if col[i]==MIN_col:
            want_col.add(i)
            
    flag=0
    for i in range(len(row)):
        if flag==1:
            break
        for j in range(len(col)):
            if grid[i][j]==".":
                if i in want_row and j in want_col:
                    flag=1
                    break
                    
    print(MIN_row+MIN_col-flag)
    
    


# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
import collections
import math

T = int(input())
 
#A,H,Q = [int(x) for x in stdin.readline().split()] 
for t in range(T):
    N,M = [int(x) for x in stdin.readline().split()]
    #print(N,M)
    data = []
    row = [M]*N
    col = [N]*M
    for i in range(N):
        s = input()
        data.append(list(s))
        for j in range(M):
            if s[j]=='*':
                row[i] -= 1
                col[j] -= 1
                
    min_row = min(row)
    min_col = min(col)
    
    if min_row==0 or min_col==0:
        print(min_row+min_col)
    else:
        r = []
        c = []
        #res = 9999999
        for i in range(N):
            if row[i]==min_row:
                r.append(i)
        for j in range(M):
            if col[j]==min_col:
                c.append(j)
                
        flag = 0
        for x in r:
            for y in c:
                if data[x][y]=='.' and flag==0:
                    print(min_row+min_col-1)
                    flag = 1
            if flag==1:
                break
                    
        if flag==0:        
            print(min_row+min_col)
                    
        
    
    
    
 


q = int(input())
for i in range(q):
    n, m = list(map(int,input().split()))
    field = [input() for j in range(n)]
    raw = [0] * n
    col = [0] * m
    num = 0
    for j in range(n):
        for z in range(m):
            if field[j][z] == "*":
                raw[j] += 1
                col[z] += 1
    for z in range(m):
        for j in range(n):
            temp = raw[j] + col[z] - int(field[j][z] == "*")
            if num < temp:
                num = temp
    print(n + m - num - 1)


def gns():
    return list(map(int,input().split()))
t=int(input())


def one():
    n, m = gns()
    mp = []
    ns = [0] * n
    ms = [0] * m
    for i in range(n):
        mp.append(input())
        for j in range(m):
            if mp[-1][j] == '*':
                ns[i] += 1
                ms[j] += 1
    min_n = max(ns)
    min_m = max(ms)
    min_ns = set([i for i in range(n) if ns[i] == min_n])
    min_ms = set([i for i in range(m) if ms[i] == min_m])
    ans = n - min_n + m - min_m
    for i in min_ns:
        for j in min_ms:
            if mp[i][j] == '.':
                print(ans - 1)
                return
    print(ans)


for i in range(t):
    one()






for TT in range(1, int(input()) + 1):
    n, m = map(int, input().split())
    mat = [[1 if c == '*' else 0 for c in input()] for _ in range(n)]
    h = [sum(l) for l in mat]
    v = [0] * m
    for i in range(n):
        for j in range(m):
            v[j] += mat[i][j]
    res = float('inf')
    for i in range(n):
        for j in range(m):
            val = (n - h[i]) + (m - v[j])
            if mat[i][j] == 0: val -= 1
            res = min(res, val)
    print(res)

import sys
input = lambda: sys.stdin.readline().strip()
print = lambda x: sys.stdout.write(f"{x}\n")

for t in range(int(input())):
  r, c = map(int, input().split())
  arr = [input() for i in range(r)]
  rarr = [0] * r
  carr = [0] * c

  for i in range(r):
    for j in range(c):
      if arr[i][j] == '.':
        rarr[i] += 1
        carr[j] += 1

  ans = float('inf')
  for i in range(r):
    for j in range(c):
      s = rarr[i] + carr[j]
      if arr[i][j] == '.':
        ans = min(ans, s - 1)
      else:
        ans = min(ans, s)
  
  print(ans)


def __starting_point():
    T = int(input())
    #fout = open('1194B.out', 'w')
    for _ in range(T):
        s = input().rstrip().split()
        n = int(s[0])
        m = int(s[1])
        cell = [[0 for j in range(m)] for i in range(n)]
        r = [0 for i in range(n)]
        c = [0 for j in range(m)]
        for i in range(n):
            s = input()
            for j in range(len(s)):
                cell[i][j] = s[j]
                if s[j] == '*':
                    r[i] += 1
                    c[j] += 1
        nmax = 0
        for i in range(n):
            for j in range(m):
                if r[i] + c[j] + (cell[i][j] == '.') > nmax:
                    nmax = r[i] + c[j] + (cell[i][j] == '.')
        print(str(m + n - nmax) + '\n')

__starting_point()

q = int(input())

for _ in range(q):
    ans = 10000000000
    n, m = list(map(int, input().split()))
    picture = []
    dotcount_w = []
    dotcount_h = []
    for _ in range(n):
        picture.append(input())
        dotcount_w.append(picture[-1].count("."))

    for i in range(m):
        count = 0
        for j in range(n):
            if picture[j][i] == ".":
                count += 1
        dotcount_h.append(count)
    for i in range(m):
        for j in range(n):
            if picture[j][i] == ".":
                ans = min(dotcount_h[i]+dotcount_w[j]-1, ans)
            else:
                ans = min(dotcount_h[i]+dotcount_w[j], ans)
    print(ans)


q = int(input())
for i in range(q):
    n,m = list(map(int,input().split()))
    a = [input() for _ in range(n)]
    a_t = list(zip(*a))
    mx_1 = mx_2 = 0
    idx_1 = []
    idx_2 = []
    for j,i in enumerate(a):
        temp = i.count('*')
        if temp > mx_1:
            mx_1 = temp
            idx_1 = [j]
        elif temp == mx_1:
            idx_1.append(j)
    for j,i in enumerate(a_t):
        temp = i.count('*')
        if temp > mx_2:
            mx_2 = temp
            idx_2 = [j]
        elif temp == mx_2:
            idx_2.append(j)
    ans = 0
    for i in idx_1:
        for j in idx_2:
            if a[i][j] == '.':
                ans = -1
    print(n+m-mx_1-mx_2+ans)



M = 10**9 + 7
R = lambda: map(int, input().split())
n = int(input())
for i in range(n):
    n,m = R()
    L = [[0 for i in range(m)] for j in range(n)]
    a = []
    for i in range(n):
        a.append(input())
    for i in range(n):
        c = 0
        for j in range(m):
            if a[i][j] == '.':c += 1
        for j in range(m):
            L[i][j] = c
    for i in range(m):
        c = 0
        for j in range(n):
            if a[j][i] == '.':c += 1
        for j in range(n):
            L[j][i] += c
    mi = 10**9
    k = []
    for i in range(n):
        for j in range(m):
            mi = min(mi,L[i][j])
    for i in range(n):
        for j in range(m):
            if L[i][j] == mi and a[i][j] == '.':
                mi -= 1
    print(mi)