Bài toán dấu cộng

Cho một bức tranh gồm $n$ hàng và $m$ cột. Các hàng được đánh số từ $1$ đến $n$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $m$ từ trái sang phải. Mỗi ô được tô màu đen hoặc trắng.

Ta gọi bức tranh là thú vị nếu trong đó có ít nhất một dấu cộng. Dấu cộng được xác định bởi một cặp số $(x,y)$ với $1\le x\le n$ và $1\le y\le m$, sao cho tất cả các ô ở hàng $x$ và tất cả các ô ở cột $y$ đều màu đen.

Bạn có một cây cọ và một hộp sơn đen. Mỗi lần, bạn có thể chọn một ô màu trắng và tô nó thành màu đen. Hãy tìm số lần tô ít nhất để bức tranh trở nên thú vị (chứa ít nhất một dấu cộng).

Bạn cần trả lời nhiều truy vấn độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $q$ là số truy vấn.
• Với mỗi truy vấn:
  • Dòng đầu chứa hai số nguyên $n$ và $m$ là số hàng và số cột.
  • $n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự, mô tả bức tranh: ký tự . nếu ô màu trắng, ký tự * nếu ô màu đen.

Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ chứa một số nguyên là đáp án cho truy vấn thứ $i$: số lần tô ít nhất để bức tranh chứa ít nhất một dấu cộng.

Ràng buộc

• $1\le q\le 5·{10}^4$
• $1\le n,m\le 5·{10}^4$ và $n·m\le 4·{10}^5$
• Tổng $n$ trên tất cả truy vấn không vượt quá $5·{10}^4$.
• Tổng $n·m$ trên tất cả truy vấn không vượt quá $4·{10}^5$.

Ví dụ