#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int NUM1=;

const int NUM2=;

const int TP=NUM2*;

const int SUM=NUM1*TP;

const int INF=;

int dx[]={,-,,};

int dy[]={,,-,};

int cnt=;

int p[NUM1][TP];

struct pair{

    int fi;

    int se;

}turn[SUM];

int pii(int a,int b){

    if(p[a][b])return p[a][b];

    cnt++;

    turn[cnt].fi=a;

    turn[cnt].se=b;

    return p[a][b]=cnt;

}

int mp[][],dis[][],pos[][];

int to[NUM1][NUM2];

bool BFS(int xx,int yy,int r,int c){

    for(int i=;i<=r;i++){

    for(int j=;j<=c;j++){

        dis[i][j]=INF;

    }

    }

    queue<int>q1,q2;

    q1.push(xx);q2.push(yy);

    dis[xx][yy]=;

    bool ok=;

    while(!q1.empty()){

    int x=q1.front(),y=q2.front();

    q1.pop();q2.pop();

    if(mp[x][y]>){

        to[pos[xx][yy]][mp[x][y]]=dis[x][y];

        ok=;

        continue;

    }

    for(int i=;i<;i++){

        int nx=x+dx[i],ny=y+dy[i];

        if(nx>r||ny>c||nx<||ny<||mp[nx][ny]==-)continue;

        if(dis[nx][ny]>dis[x][y]+){

        dis[nx][ny]=dis[x][y]+;

        q1.push(nx);q2.push(ny);

        }

    }

    }

    return ok;

}

bool vis[TP],a[NUM1][TP];

int shu[TP];

bool dfs(int i){

    for(int j=;j<=cnt;j++){

        if(a[i][j]&&!vis[j]){

            vis[j]=;

            if(!shu[j]||dfs(shu[j])){

                shu[j]=i;

                return ;

            }

        }

    }

    return ;

}

int num1,num2;

bool pan(int t){

    memset(shu,,sizeof(shu));

    int ans=;

    for(int i=;i<=num1;i++){

    memset(vis,,sizeof(vis));

    if(dfs(i))ans++;

    }

    if(ans!=num1)return ;

    return ;

}

void restart(){

    cnt=;

    num1=;

    num2=;

    memset(a,,sizeof(a));

    memset(p,,sizeof(p));

    memset(to,,sizeof(to));

    memset(mp,,sizeof(mp));

    memset(pos,,sizeof(pos));

    return;

}

int main(){

    int N;

    cin>>N;

    while(N--){

    restart();

    int r,c;

    cin>>r>>c;

    for(int i=;i<=r;i++){

        for(int j=;j<=c;j++){

        char ch;cin>>ch;

        if(ch=='X')mp[i][j]=-;

        else if(ch=='.'){

            num1++;

            pos[i][j]=num1;

        }else mp[i][j]=;

        }

    }

    for(int i=;i<=r;i++){

        for(int j=;j<=c;j++){

        if(mp[i][j]==){

            num2++;

            mp[i][j]=num2;

        }

        }

    }

    bool ha=;

    for(int i=;i<=r;i++){

        for(int j=;j<=c;j++){

        if(!mp[i][j]){

            if(!BFS(i,j,r,c)){

            cout<<"impossible"<<endl;

            ha=;

            break;

            }

        }

        }

        if(ha)break;

    }

    if(ha)continue;

    for(int i=;;i++){

        for(int j=;j<=num1;j++){

        for(int k=;k<=num2;k++){

            if(to[j][k]&&to[j][k]<=i){

            a[j][pii(k,i)]=;

            }

        }

        }

        if(pan(i)){

        cout<<i<<endl;

        break;

        }

    }

    }

    return ;

}