We can calculate the size of a “plus of pluses” shape from its center where the vertical and horizontal lines intersect. In other words we can go through each and every ‘+’ sign in the grid and calculate how many consecutive ‘+’ sign are there in 4 direction. This can be calculated in many ways in constant time. We need to precalculate four N*M 2D arrays where each will store the number of consecutive ‘+’ signs in each direction. We will take the minimum of four directions and multiply by four.

time complexity : \(O(N*M)\)

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
// complexity O(n*m)
#include<bits/stdc++.h>
using namespace std;
char a[2002][2002];
int lft[2002][2002],rt[2002][2002],up[2002][2002],down[2002][2002];
int n,m;

int solve() //storing the index of first '-' in four directions. complexity: O(N*M)
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++) cin>> a[i][j];
    }
    stack<int>st;
    // right
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='+') st.push(j);
            else
            {
                while(st.size()) {rt[i][st.top()] = j;  st.pop();}
            }
        }
        while(st.size()) {rt[i][st.top()]=m; st.pop();}
    }
    // left
    for(int i=0;i<n;i++)
    {
        for(int j=m-1;j>=0;j--)
        {
            if(a[i][j]=='+') st.push(j);
            else
            {
                while(st.size()) {lft[i][st.top()] = j;  st.pop();}
            }
        }
        while(st.size()) {lft[i][st.top()]=-1;  st.pop();}
    }
    // down
    for(int j=0;j<m;j++)
    {
        for(int i=0;i<n;i++)
        {
            if(a[i][j]=='+') st.push(i);
            else
            {
                while(st.size()) {down[st.top()][j] = i;  st.pop();}
            }
        }
        while(st.size()) {down[st.top()][j] = n;  st.pop();}
    }
    // up
    for(int j=0;j<m;j++)
    {
        for(int i=n-1;i>=0;i--)
        {
            if(a[i][j]=='+') st.push(i);
            else
            {
                while(st.size()) {up[st.top()][j] = i;  st.pop();}
            }
        }
        while(st.size()) {up[st.top()][j] = -1;  st.pop();}
    }
    int ans = 0,u,d,l,r;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='-') continue;
            u = (i-up[i][j])-1;
            d = (down[i][j]-i)-1;
            l = (j-lft[i][j])-1;
            r = (rt[i][j]-j)-1;
            ans = max(ans,4*min({u,d,l,r})+1);
        }
    }
    return ans;
    //cout<<ans<<endl;
}


int solve2() // binary search on prefixsum, complexity O(N*M*log(N+M))
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++) cin>> a[i][j];
    }
    for(int i=0;i<n;i++)
    {
        rt[i][0] = (a[i][0]=='+');
        for(int j=1;j<m;j++) rt[i][j] = rt[i][j-1]+(a[i][j]=='+');
    }
    for(int i=0;i<n;i++)
    {
        lft[i][m-1] = (a[i][m-1]=='+');
        for(int j=m-2;j>=0;j--) lft[i][j] = lft[i][j+1]+(a[i][j]=='+');
    }
    for(int j=0;j<m;j++)
    {
        down[0][j] = (a[0][j]=='+');
        for(int i=1;i<n;i++) down[i][j] = down[i-1][j]+(a[i][j]=='+');
    }
    for(int j=0;j<m;j++)
    {
        up[n-1][0] = (a[n-1][0]=='+');
        for(int i=n-2;i>=0;i--) up[i][j] = up[i+1][j]+(a[i][j]=='+');
    }
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='-') continue;
            int lftc=0, rtc=0, upc = 0, downc=0,lo,hi,mid,cnt;
            // right
            lo = 0; hi=m-j-1;
            while(lo<=hi)
            {
                mid = (lo+hi)>>1;
                if(rt[i][j+mid] == rt[i][j]+mid) rtc = mid, lo = mid+1;
                else hi = mid-1;
            }
            // left
            lo = 0; hi = j;
            while(lo<=hi)
            {
                mid = (lo+hi)>>1;
                if(lft[i][j-mid] == lft[i][j]+mid) lftc = mid, lo = mid+1;
                else hi = mid-1;
            }
            // up
            lo = 0; hi = i;
            while(lo<=hi)
            {
                mid= (lo+hi)>>1;
                if(up[i-mid][j] == up[i][j]+mid) upc = mid, lo = mid+1;
                else hi = mid-1;
            }
            // dwn
            lo = 0; hi = n-i-1;
            while(lo<=hi)
            {
                mid = (lo+hi)>>1;
                if(down[i+mid][j] == down[i][j]+mid) downc = mid, lo = mid+1;
                else hi = mid-1;
            }

            ans = max( ans , 4 * min({lftc,upc,rtc,downc}) + 1);
        }
    }
    return ans;
}

int solve3() // modified prefix sum, complexity O(N*M)
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>> a[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) lft[i][j] = (a[i][j]=='+')? lft[i][j-1]+1 : 0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--) rt[i][j] = (a[i][j]=='+')? rt[i][j+1]+1 : 0;
    }
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=n;i++) up[i][j] = (a[i][j]=='+')? up[i-1][j]+1 : 0;
    }
    for(int j=1;j<=m;j++)
    {
        for(int i=n;i>=1;i--) down[i][j] = (a[i][j]=='+')? down[i+1][j]+1 : 0;
    }

    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='-') continue;
            ans = max(ans , min({lft[i][j],rt[i][j],up[i][j],down[i][j]})*4-3);
        }
    }
    return ans;
}

int main()
{
    int t; cin>>t; while(t--) cout<<solve3()<<'\n';
}