## Problem

time limit per test : 2 seconds
memory limit per test : 256 megabytes
input : standard input
output : standard output

### Description

You are given a picture consisting of $nn$ 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≤x≤n$ and $1≤y≤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: The fourth picture contains 4 crosses: at $(1,3)$ , (1,5)(1,5), $(3,3)$ and $(3,5)$ .

Following images don’t contain crosses: 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?

### Input

The first line contains an integer $q$ (1≤q≤5⋅1041≤q≤5⋅104) — the number of queries.

The first line of each query contains two integers $nn$ and $m$ (1≤n,m≤5⋅1041≤n,m≤5⋅104, n⋅m≤4⋅105n⋅m≤4⋅105) — the number of rows and the number of columns in the picture.

Each of the next $nn$ lines contains $m$ characters — ‘.’ if the cell is painted white and ‘*’ if the cell is painted black.

It is guaranteed that $\sum n\le5\times10^4, \sum n\times m \le 4 \times 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

#### output

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 66-th picture to get a cross in $(3,3)$ . That’ll take you 44 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 88-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 33 minutes instead of $1$ .

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

❤采之欲遗谁，所思在远道。❤
0%