hyoi AK IOI

#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>
using namespace std;
const int N = 503;

struct stu{
	int x,y;
};

int T;
int n,m;
int st[N][N];
int dis[N][N];
char g[N][N];
int dx[4] = {-1,-1,1,1};
int dy[4] = {-1,1,1,-1};
int ix[4] = {-1,-1,0,0};
int iy[4] = {-1,0,0,-1};
char cs[5] = "\\/\\/";

int bfs()
{
	memset(st,0,sizeof st);
	memset(dis,0x3f,sizeof dis);
	deque <stu> que;
	stu s;
	s.x = 0;
	s.y = 0;
	que.push_back(s);
	dis[0][0] = 0;
	while(que.size())
	{
		stu t = que.front();
		que.pop_front();
		int x = t.x;
		int y = t.y;
		if(x == n && y == m) return dis[x][y];
		if(st[x][y]) continue;
		st[x][y] = 1;
		for(int i = 0;i < 4;i ++)
		{
			int a = x + dx[i];
			int b = y + dy[i];
			if(a < 0 || b < 0 || a > n || b > m) continue;
			int ga = x + ix[i];
			int gb = y + iy[i];
			int w = (g[ga][gb] != cs[i]);
			if(dis[x][y] + w <= dis[a][b])
			{
				dis[a][b] = dis[x][y] + w;
				stu temp;
				temp.x = a;
				temp.y = b;
				if(!w) que.push_front(temp);
				else que.push_back(temp);
			}
		}
	}
}

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