本题有个很好的性质,就是到不了和为奇数的点,因为每次移动要么+2要么-2要么为0 QAQ
有了这个性质,我们就知道一条边最多变化一次.这样就不用考虑后效性了.
然后我们用点权做bfs,把点权为x的进行扩展,点权为x+1的放置.
由于一个点可能被多次扩展,可能被同一点权的不同点扩展所产生2种不同代价且后者小于前者,所以我们要取min.
已经扩展的点不需要第二次扩展,我们直接标记就好了,

include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
const int N=505;
char an[N][N];
int val[N][N],n,m;//每个点的最小代价
bool st[N][N];//看是否每个点用过
int d[4][2]={{-1,-1},{-1,1},{1,-1},{1,1}};
int mi[4][2]={{-1,-1},{-1,0},{0,-1},{0,0}};
char ck[]="\\//\\";
int bfs()
{
    memset(val,0x3f,sizeof val);
    memset(st,false,sizeof st);
    deque<pi>q;
    val[1][1]=0;
    q.push_front({1,1});
    while(q.size())
    {
        auto temp=q.front();
        q.pop_front();
        int x=temp.first;int y=temp.second;
        if(st[x][y]) continue;
        st[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int a=x+d[i][0];int b=y+d[i][1];
            if(a<1||a>n+1||b<1||b>m+1) continue;
            int ca=x+mi[i][0],cb=y+mi[i][1];
            int z=val[x][y]+(an[ca][cb]!=ck[i]);
            if(z<val[a][b])
            {
                val[a][b]=z;
                if(an[ca][cb]==ck[i]) q.push_front({a,b});
                else q.push_back({a,b});
            }

        }
    }
    return val[n+1][m+1];
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;   
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>an[i][j];
            }
        }
        if((n+m)&1) puts("NO SOLUTION");
        else      cout<<bfs()<<endl;
    }
    return 0;
}