Untitled

#include<iostream>
using namespace std;

char a[20][20];

int X[4] = { 1,-1, 0, 0};
int Y[4] = { 0, 0, 1, -1};

int cnt;
int m,n;
bool checkT;

bool xet(int x, int y){
	
	cnt =0;
	for(int i=0; i<4; i++){
		int u =y+X[i];
		int v =x+Y[i];
		if(u>=0 && u < m && v >=0 && v <m){
		if(a[u][v] == '.'){
			if(u == 0 || u == m-1 || v==0 || v== n-1){
			cnt++;
			}
			else{
			a[u][v] = '#';
			xet(u,v);
			}
		}
		}
	}
	
		return cnt;
}

int main(){
	int test;
	cin >> test;
	//freopen("text.txt", "r", stdin);
	for(int tc= 1; tc <= test; tc++){
		a[20][20] = {0};
		cin >> m >> n;

		for(int i=0; i < m; i++){
			for(int j= 0; j < n; j++){
				cin >> a[i][j];
			}
		}
		int checkT = 0;
		
	
		//xet xung quanh
		for(int i=0; i < m; i++){
			for(int j= 0; j < n; j++){
				if(i == 0 || i == m-1 || j == 0 || j == n-1){
					if(a[i][j] == '.'){
						checkT = xet(i,j);
					}
				}
			}
		}
		if(checkT == 2) cout << "valid"  << endl;
		else cout <<  "invalid"  << endl;
	}
	return 0;
}