Untitled

#include<iostream>
using namespace std;
int rear, front;
struct toado{int x,y;};
toado queue[10000000];
void init(){rear=0; front=0;}
void push(int x,int y) {queue[rear].x=x;queue[rear].y=y;rear++;}
toado pop(){toado t=queue[front];front++;return t;}

int T, hang, cot;
int arr[25][25], visit[25][25], vt[25][2];
int rs, flag, sav;
char a;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void nhap(){
	sav = 0;
	cin >> hang >> cot;
	for(int i = 0; i < hang; i ++) {
		for(int j = 0; j < cot; j ++) {
			cin >> a;
			if(a == '.') arr[i][j] = 0;
			else if(a == '#') arr[i][j] = 1;
			if(i == 0 || i == hang - 1 || j == 0 || j == cot-1) {
				if(!arr[i][j]) {
					vt[sav][0] = i; vt[sav][1] = j;
					sav ++;
				}
			}
		}
	}
}
void reset() {
	for(int i = 0; i < hang; i ++) {
		for(int j = 0; j < cot; j ++) visit[i][j] = 0;
	}
}
bool cdk(int x, int y){
	if(x >= 0 && x < hang && y >= 0 && y < cot) return true;
	return false;
}
void bfs(int x, int y) {
	init();
	visit[x][y] = 1;
	push(x,y);
	while(front<rear) {
		toado t = pop();
		for(int i = 0; i < 4; i ++) {
			int xx = t.x + dx[i];
			int yy = t.y + dy[i];
			if(cdk(xx,yy) && !visit[xx][yy] && !arr[xx][yy]) {
				visit[xx][yy] = 1;
				push(xx,yy);
			}
		}
		if(visit[vt[1][0]][vt[1][1]]) {
			cout << "valid" << endl;
			return;
		}
	}
	cout << "invalid" << endl;
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin >> T;
	for(int t = 1; t <= T; t ++) {
		nhap(); reset();
		if(sav == 2) {
			bfs(vt[0][0],vt[0][1]);
		}
		else cout << "invalid" << endl;
	}
	return 0;
}