// i wants to take ioi
//binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define nn "\n"
#define pi pair<int, int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define TASK " "

#define ms(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define All(a, n) a + 1, a + 1 + n

#define LOG 19


const int INF = 1e18;
const int mod = 1e9;
const int N = 20  + 5;
int MOD = 998244353;
int bit[200000];
struct node{
	int kc, u, hk;
	bool operator<(const node& other) const {
        return kc > other.kc;
    }
};
struct edge{
	int v, w, h;
};

void nhap(){

}
char a[N][N];
bool vis[N][N];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int m, n;
bool bfs(int sx, int sy){
    queue<pi> q;
    q.push({sx, sy});
    vis[sx][sy] = 1;
    while(!q.empty()){
        int u = q.front().fi, v = q.front().se;
        q.pop();
        if((u == 1 || u == m || v == 1 || v == n) && a[u][v] == '.' && (u != sx || v != sy)){
            return 1;
        }
        for(int i = 0; i < 4; i++){
            int x = u + dx[i];
            int y = v + dy[i];
            if(x < 1 || y < 1 || x > m || y > n || a[x][y] == '#') continue;
            if(!vis[x][y]){
                vis[x][y] = 1;
                q.push({x, y});
            }
        }
    }
    return 0;
}
void solve(){
    cin >> m >> n;
    for(int i = 1; i <= m; i++){
        for(int j= 1; j <= n; j++){
            cin >> a[i][j];
            vis[i][j] = 0;
        }
    }
    bool ok = 0;
    vector<pi> v;

    for(int i = 1; i <= m; i++){
        if(a[i][1] == '.'){
            v.eb(i, 1);
        }
        if(a[i][n] == '.'){
            v.eb(i, n);
        }
    }
    for(int i = 1; i <= n; i++){
        if(a[1][i] == '.'){
            v.eb(1, i);
        }
        if(a[m][i] == '.'){
            v.eb(m, i);
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    if(v.size() == 2){
        if(bfs(v[0].fi, v[0].se)){
            cout << "valid" << nn;
        }
        else cout << "invalid" << nn;
    }
    else cout << "invalid" << nn;

}
signed main() {
//	 freopen("m_mu_n.inp", "r", stdin);
//	 freopen("m_mu_n.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t; cin >> t;
    while(t--) solve();
	return (0 ^ 0);

}