hdu-2579

using namespace std;
const int kMaxN = 100;
struct {
    int x, y;
    int step;
    Point(int a, int b, int s = 0) : x(a), y(b), step(s){}
};
int kT, kN, kM;
char kMap[kMaxN][kMaxN];
int kVis[kMaxN][kMaxN][10];
int kSX, kSY, kEX, kEY, kK;
const int kDx[4] = {0, 1, -1, 0};
const int kDy[4] = {1, 0, 0, -1};
void Input(){
    for(int i = 0; i < kN; ++i){
        scanf("%s", kMap[i]);
        for(int j = 0; j < kM; ++j){
            if(kMap[i][j] == 'Y'){
                kSX = i, kSY = j;
            }
            if(kMap[i][j] == 'G'){
                kEX = i, kEY = j;
            }
        }
    }
}
bool Ok(int nx, int ny, int step){
    if(nx >= 0 && nx < kN && ny >= 0 && ny < kM && !kVis[nx][ny][step%kK]){
        return true;
    }
    return false;
}
void Bfs(){
    Point p(kSX, kSY);
    queue<Point>que;
    que.push(p);
    memset(kVis, false, sizeof(kVis));
    kVis[kSX][kSY][0] = true;
    while(!que.empty()){
        Point top = que.front();
        if(top.x == kEX && top.y == kEY){
            cout<<top.step<<endl;
            return;
        }
        que.pop();
        for(int i = 0; i < 4; ++i){
            int nx = top.x + kDx[i];
            int ny = top.y + kDy[i];
            int step = top.step + 1;
            if(Ok(nx, ny, step)){
                if(kMap[nx][ny] == '#' && step % kK == 0 ){
                    kVis[nx][ny][0] = true;
                }
                else if(kMap[nx][ny] == '#' && step % kK != 0){
                    continue;
                }
                else {
                    kVis[nx][ny][step % kK] = true;
                }
                que.push(Point(nx, ny, step));
            }
        }
    }
    puts("Please give me another chance!");
}
int main(){
    cin>>kT;
    while(kT--){
        cin>>kN>>kM>>kK;
        Input();
        Bfs();
    }
    return 0;
}