#include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <queue>
    #include <vector>

    using namespace std;

    struct tocka{
        int x, y;
        tocka(){ x = 0; y = 0; }


        tocka( int _x, int _y ){
            x = _x; y = _y;
        }
    };

    const int maxn = 200;

    int T, N, M;
    char a[ maxn ][ maxn ];

    tocka P, D;
    vector< tocka > zvjezdice;
    bool posjetio = false;

    int bio[ maxn ][ maxn ];
    queue< tocka > Q;
    const int dx[] = { 0, 1, 0, -1 };
    const int dy[] = { -1, 0, 1, 0 };

    bool ok( tocka tmp ){
        if( tmp.x < 0 || tmp.y < 0 ) return false;
        if( tmp.x >= N || tmp.y >= M ) return false;
        if( a[ tmp.x ][ tmp.y ] == '#' ) return false;
        if( bio[ tmp.x ][ tmp.y ] != -1 ) return false;
        return true;
    }

    void bfs(){
        memset( bio, -1, sizeof bio );
        posjetio = false;

        bio[ P.x ][ P.y ] = 0;
        for( Q.push( P ); !Q.empty(); Q.pop() ){
            tocka t = Q.front();

            if( a[ t.x ][ t.y ] == '*' && !posjetio ){
                for( int i = 0; i < zvjezdice.size(); i ++ ){
                    if( bio[ zvjezdice[ i ].x ][ zvjezdice[ i ].y ] == -1 ){
                        Q.push( zvjezdice[ i ] );
                        bio[ zvjezdice[ i ].x ][ zvjezdice[ i ].y ] = bio[ t.x ][ t.y ] + 1;
                    }
                }

                posjetio = true;
            }

            for( int i = 0; i < 4; i ++ ){
                tocka tmp = tocka( t.x + dx[ i ], t.y + dy[ i ] );

                if( ok( tmp ) ){
                    Q.push( tmp );
                    bio[ tmp.x ][ tmp.y ] = bio[ t.x ][ t.y ] + 1;
                }
            }
        }

        return;
    }

    void ucitaj(){
        scanf( "%d%d", &N, &M );
        for( int i = 0; i < N; i ++ ){
            cin >> a[ i ];
            for( int j = 0; j < M; j ++ ){
                if( a[ i ][ j ] == 'P' ) P = tocka( i, j );
                if( a[ i ][ j ] == 'D' ) D = tocka( i, j );
                if( a[ i ][ j ] == '*' ) zvjezdice.push_back( tocka( i, j ) );
            }
        }
        return;
    }

    int main( void ){
        scanf( "%d", &T );
        for( int i = 0; i < T; i ++ ){
            zvjezdice.clear();

            ucitaj();
            bfs();

            if( bio[ D.x ][ D.y ] > -1 && zvjezdice.size() != 1 ) printf( "Case %d: %d\n", i + 1, bio[ D.x ][ D.y ] );
            else printf( "Case %d: impossible\n", i + 1 );
        }
    return 0;
    }