DFS+map+set

#include<iostream>
#include<map>
#include<set>
#include<cstdio>
#define pa pair<int,int>
#define mk make_pair
using namespace std;

const int maxn = 1e3 + 15;
bool a[maxn][maxn];
pa res[maxn][maxn];
int n,m,vis[maxn][maxn],stamp,ax[5] = {0,1,-1,0,0},ay[5] = {0,0,0,1,-1};
map<pa,int> mp;
void input(){
mp.clear();
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
char c;
cin >> c;
a[i][j] = (c == '#' ? 1 : 0);
}
}
}
bool check(int x,int y){
if(x < 1 || y < 1 || x > n || y > m || vis[x][y] == stamp || a[x][y] == 0) return 0;
return 1;
}
bool check1(int x,int y){
if(x < 1 || y < 1 || x > n || y > m || a[x][y] == 0) return 0;
return 1;
}
void dfs(pa h,int x,int y){
mp[h];
vis[x][y] = stamp;
res[x][y] = h;
for(int i = 1;i <= 4;i){
int nx = x + ax[i],ny = y + ay[i];
if(!check(nx,ny)) continue;
dfs(h,nx,ny);
}
}
int test1(int x){
int ans = 0;
set<pa> st;
for(int i = 1;i <= m;i++){
if(a[x][i]){
st.insert(res[x][i]);
}
else{
ans++;
for(int j = 1;j <= 4;j++){
int nx = x + ax[j],ny = i + ay[j];
if(!check1(nx,ny)) continue;
st.insert(res[nx][ny]);
}
}
}
for(auto i : st) ans += mp[i];
return ans;
}
int test2(int x){
int ans = 0;
set<pa> st;
for(int i = 1;i <= n;i++){
if(a[i][x]){
st.insert(res[i][x]);
}
else{
ans++;
for(int j = 1;j <= 4;j++){
int nx = i + ax[j],ny = x + ay[j];
if(!check1(nx,ny)) continue;
st.insert(res[nx][ny]);
}
}
}
for(auto i : st) ans += mp[i];
return ans;
}
void solve(){
int ans = 0;
input();
stamp++;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(vis[i][j] != stamp && a[i][j]){
mp[mk(i,j)] = 0;
dfs(mk(i,j),i,j);
}
}
}
for(int i = 1;i <= n;i++) ans = max(ans,test1(i));
for(int i = 1;i <= m;i++) ans = max(ans,test2(i));
cout << ans << endl;
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}

return 0;

}