Zombie Blast

#include<bits/stdc++.h>
using namespace std;

#define sc( x ) scanf( "%d" , &x )
#define REP( i , n ) for( int i = 0 ; i < n ; ++i )
#define clr( t , val ) memset( t , val , sizeof( t ) )

#define pb push_back
#define all( v ) v.begin() , v.end()
#define SZ( v ) ((int)(v).size())

#define mp make_pair
#define fi first
#define se second

#define N 2000

#define sqr(A) ((A)*(A))
#define test puts( "********************test***************" );

typedef long long ll;
double eps = 1e-8;
int cmp (double a , double b = 0 ){
        return a + eps < b ? -1 : a - eps > b ? 1 : 0 ;
}
struct point {
    ll x , y ;
    point ( ll a , ll b ) : x ( a ) , y ( b ){ }
    point () {}
    point operator + ( point p ){ return point ( x + p.x , y + p.y ) ; }
    point operator - ( point p ){ return point ( x - p.x , y - p.y ) ; }
    point operator * ( ll t ){ return point ( x * t , y * t ) ; }
    double operator * ( point p ){ return x * p.x + y * p.y ; }
    double operator % ( point p ){ return x * p.y - y * p.x ; }
    bool operator == ( point p ){ return cmp ( x , p.x ) == 0 && cmp ( y , p.y ) == 0 ; }
    bool operator < ( point p ) const{
            int t = cmp ( x , p . x ) ;
            if ( t ) return t < 0 ;
            return cmp ( y , p . y ) < 0 ;
    }
} ;
point T[ N * N + 5 ];
int le[ N * N + 5 ] , ri[ N * N + 5 ];
bool compx( const point &A , const point &B ){
    return A.x < B.x;
}
bool compy( const point &A , const point &B ){
    return A.y < B.y;
}

//intervalocerrado[from,to]
inline int make( int from , int to , bool byx = true ){
    if( from > to ) return -1;
    if( from == to ){
        le[ from ] = ri[ from ] = -1;
        return from;
    }
    int mid=(from + to)/2;
    nth_element( T + from , T + mid , T + to + 1 , byx ? compx : compy );
    le[ mid ] = make( from , mid - 1 , !byx );
    ri[ mid ] = make( mid + 1 , to , !byx );
    return mid;
}
/*
inline int make( int from , int to , bool byx = true ){
    if( from >= to ) return -1;
    if( from + 1 == to ){
        le[ from ] = ri[ from ] = -1;
        return from;
    }
    int mid = (from + to)/2;
    nth_element( T + from , T + mid , T + to , byx ? compx : compy );
    le[ mid ] = make( from , mid , !byx );
    ri[ mid ] = make( mid , to , !byx );
    return mid;
}
*/
point p;
ll dist;

//busco la distancia al nodo mas cercano de p.
//dist tiene q ser puesta en inf antes de hacer la query.
void query( int node , bool bxy ){
    if( node == -1 ) return;
    ll distnode = sqr( T[ node ].x - p.x ) + sqr( T[ node ].y - p.y );
    dist = min( dist , distnode );
    if( bxy ){
        ll len = sqr( T[ node ].x - p.x );
        if( compx( T[ node ] , p ) ){
            query( ri[ node ] , !bxy );
            if( len <= dist )
                query( le[ node ] , !bxy );
        }else{
            query( le[ node ] , !bxy );
            if( len <= dist )
                query( ri[ node ] , !bxy );
        }
    }else{
        ll len = sqr( T[ node ].y - p.y );
        if( compy( T[ node ] , p ) ){
            query( ri[ node ] , !bxy );
            if( len <= dist )
                query( le[ node ] , !bxy );
        }else{
            query( le[ node ] , !bxy );
            if( len <= dist )
                query( ri[ node ] , !bxy );
        }
    }
}
char S[ N + 5 ][ N + 5 ];
int main(){
    int cases , n , m;
    sc( cases );
    REP( tc , cases ){
        sc( m ) , sc( n );
        REP( i , n ) scanf( "%s" , S[ i ] );
        int len = 0;
        REP( i , n )REP( j , m )
            if( S[ i ][ j ] == 'M' ) {
                T[ len ++ ] = point( i , j );
                //cout << i << " " << j << endl;
            }
        int root = make( 0 , len );
        ll ans = 0;
        //cout << root << endl;
        REP( i , n )REP( j , m )if( S[ i ][ j ] == 'Z' ){
            dist = 1 << 30;
            //cout << i << " " << j << endl;
            p = point( i , j );
            query( root , 1 );
            //cout << dist << endl;
            ans = max( ans , dist );
        }
        printf( "%.10f\n" , sqrt( ans ) );
    }

}