HR 101 Feb #3

# Enter your code here. Read input from STDIN. Print output to STDOUT

T = input()

DOWN = 1
RIGHT = 1j
UP, LEFT = -DOWN, -RIGHT


def add(x, y):
    return x[0] + y[0], x[1] + y[1]

def find_coords(forest, N, M):

    she, exit = 'M', '*'

    she_pos, exit_pos = False, False

    for row in xrange(N):
        if not she_pos:
            col = forest[row].find(she)
            if col > -1:
                she_pos = row, col

        if not exit_pos:
            col = forest[row].find(exit)
            if col > -1:
                exit_pos = row, col

    return she_pos, exit_pos


def imag_coords(z):
    return int(z.real), int(z.imag)


def get_cell(forest, coords, N, M):

    i, j = coords

    return (0 <= i < N and 0 <= j < M and forest[i][j]) or 'X'


def is_correct(forest, she, exit, K, _from = None):
    if she == exit and K == 0:
        return True
    elif K < 0:
        return False

    paths = possible_paths(forest, she, _from)
    length = len(paths)

    #print she, K, _from, paths

    if length == 0:  # no exit
        return False
    elif length == 1:
        return is_correct(forest, add(she, imag_coords(paths[0][0])), exit, K, paths[0][1])
    else:
        res = False

        for path in paths:
            res = res or is_correct(forest, add(she, imag_coords(path[0])), exit, K - 1, path[1])

        return res


def possible_paths(forest, she, _from):

    TREE = 'X'
    valid = lambda cell: get_cell(forest, cell, N, M) != TREE

    dirs = [LEFT, RIGHT, UP, DOWN]

    possible = [(dir, -dir) for dir in dirs if valid(add(she, imag_coords(dir))) and dir != _from]

    return possible


def solution(forest, she, exit, K):

    OK, FAIL = 'Impressed', 'Oops!'

    return OK if is_correct(forest, she, exit, K) else FAIL



for t in xrange(T):

    N, M = (int(x) for x in raw_input().split())

    forest = [raw_input() for i in xrange(N)]

    K = input()

    she, exit = find_coords(forest, N, M)

    print solution(forest, she, exit, K)