Ron and Hermione are deep in the Forbidden Forest collecting potion ingredients, and they've managed to lose their way. The path out of the forest is blocked, so they must make their way to a portkey that will transport them back to Hogwarts.  

Consider the forest as an $N\times M$ grid. Each cell is either empty (represented by .) or blocked by a tree (represented by $\mbox{X}$). Ron and Hermione can move (together inside a single cell) LEFT, RIGHT, UP, and DOWN through empty cells, but they cannot travel through a tree cell. Their starting cell is marked with the character $\mbox{M}$, and the cell with the portkey is marked with a $*$. The upper-left corner is indexed as $(0,0)$. 

.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.

In example above, Ron and Hermione are located at index $(2,7)$ and the portkey is at $(1,2)$. Each cell is indexed according to Matrix Conventions.    

Hermione decides it's time to find the portkey and leave. They start along the path and each time they have to choose a direction, she waves her wand and it points to the correct direction. Ron is betting that she will have to wave her wand exactly $\boldsymbol{\mbox{k}}$ times. Can you determine if Ron's guesses are correct?

The map from above has been redrawn with the path indicated as a series where $\mbox{M}$ is the starting point (no decision in this case), $1$ indicates a decision point and $0$ is just a step on the path:

.X.X.10000X
.X*0X0XXX0X
.XX0X0XM01.
...100XXXX.

There are three instances marked with $1$ where Hermione must use her wand.

Note: It is guaranteed that there is only one path from the starting location to the portkey.  

Function Description  

Complete the countLuck function in the editor below.  It should return a string, either $\textbf{Impressed}$ if Ron is correct or $\mathsf{0ops!}$ if he is not.  

countLuck has the following parameters:  

matrix: a list of strings, each one represents a row of the matrix  
k: an integer that represents Ron's guess  

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.

Each test case is described as follows: 

The first line contains $2$ space-separated integers $n$ and $m$, the number of forest matrix rows and columns. 

Each of the next $n$ lines contains a string of length $m$ describing a row of the forest matrix. 

The last line contains an integer $\boldsymbol{\mbox{k}}$, Ron's guess as to how many times Hermione will wave her wand.

Constraints

$1\leq t\leq10$  
$1\le n,m\le100$  
$0\leq k\leq10000$  
There will be exactly one $\mbox{M}$ and one $*$ in the forest.  
Exactly one path exists between $\mbox{M}$ and $*$.

Output Format

On a new line for each test case, print $\textbf{Impressed}$ if Ron impresses Hermione by guessing correctly.  Otherwise, print $\mathsf{0ops!}$.

Sample Input
3
2 3
*.M
.X.
1
4 11
.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.
3
4 11
.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.
4

Sample Output
Impressed
Impressed
Oops!

Explanation

For each test case, $\textit{count}$ denotes the number of times Hermione waves her wand.    

Case 0: Hermione waves her wand at $(0,2)$, giving us $count=1$. Because $count=k=1$, we print $\textbf{Impressed}$ on a new line. 

Case 1: Hermione waves her wand at $(2,9)$, $(0,5)$, and $(3,3)$, giving us $count=3$. Because $count=k=3$, we print $\textbf{Impressed}$ on a new line. 

Case 2: Hermione waves her wand at $(2,9)$, $(0,5)$, and $(3,3)$, giving us $count=3$. Because $count=3$ and $k=4$, $count\neq k$ and we print $\mathsf{0ops!}$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
T = int(input())

def find(matrix, char):
	char_row = [row for row in range(len(matrix)) if char in matrix[row]][0]
	char_col = matrix[char_row].index(char)
	return (char_row, char_col)

def sum_coords(a, b):
	return (a[0] + b[0], a[1] + b[1])

def find_path(matrix):
	(N, M) = (len(matrix), len(matrix[0]))
	start = find(matrix, 'M')
	end = find(matrix, '*')
	paths = [[start]]

	def get(coord):
		return matrix[coord[0]][coord[1]]
	while paths:
		new_paths = []
		for path in paths:
			for delta in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				coord = sum_coords(path[-1], delta)
				if 0 <= coord[0] < N and 0 <= coord[1] < M and (len(path) == 1 or coord != path[-2]) and (get(coord) != 'X'):
					if coord == end:
						return path + [coord]
					else:
						new_paths.append(path + [coord])
		paths = new_paths
	return None

def count_waves(matrix, path):
	(N, M) = (len(matrix), len(matrix[0]))

	def get(coord):
		return matrix[coord[0]][coord[1]]
	count = 0
	for (i, path_coord) in enumerate(path[:-1]):
		neighbors = [sum_coords(path_coord, delta) for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]]
		options = [coord for coord in neighbors if 0 <= coord[0] < N and 0 <= coord[1] < M and (get(coord) != 'X')]
		if len(options) > (2 if i > 0 else 1):
			count += 1
	return count
for _i in range(T):
	(N, M) = map(int, input().split())
	matrix = []
	for row in range(N):
		matrix.append(input())
	K = int(input())
	path = find_path(matrix)
	count = count_waves(matrix, path)
	print('Impressed' if K == count else 'Oops!')


class Grid:

	def __init__(self, s):
		self.g = [[c for c in r] for r in s.split()]
		self.height = len(self.g)
		self.width = len(self.g[0])

	def get(self, pos):
		return self.g[pos[0]][pos[1]]

	def set(self, pos, what):
		if self.g[pos[0]][pos[1]] not in 'M*':
			self.g[pos[0]][pos[1]] = what

	def find(self, c):
		for (i, r) in enumerate(self.g):
			if c in r:
				return (i, r.index(c))

	def neighbors(self, pos):
		candidates = [(pos[0], pos[1] - 1), (pos[0], pos[1] + 1), (pos[0] - 1, pos[1]), (pos[0] + 1, pos[1])]
		return [c for c in candidates if 0 <= c[0] < self.height and 0 <= c[1] < self.width]

def wands(grid):
	pos = grid.find('M')
	path = [pos] + visit(grid, pos)
	wandcount = 0
	for p in path[:-1]:
		neighbors = grid.neighbors(p)
		unvisited = [n for n in neighbors if grid.get(n) in '.-']
		if len(unvisited) > 0:
			wandcount += 1
	return wandcount

def visit(grid, pos):
	neighbors = grid.neighbors(pos)
	grid.set(pos, '-')
	for n in neighbors:
		if grid.get(n) == '.':
			res = visit(grid, n)
			if res:
				grid.set(pos, '=')
				return [n] + res
		elif grid.get(n) == '*':
			grid.set(pos, '=')
			return [n]
	return None
T = int(input())
for _ in range(T):
	N = int(input().split()[0])
	gridstr = '\n'.join((input() for _ in range(N)))
	g = Grid(gridstr)
	K = int(input())
	if wands(g) == K:
		print('Impressed')
	else:
		print('Oops!')


def search(coordinate, wand=0):
	visited.append(coordinate)
	moves = []
	if grid[coor(coordinate)] == '*':
		return wand
	if coordinate[0] > 1:
		a = [coordinate[0] - 1, coordinate[1]]
		if grid[coor(a)] != 'X' and a not in visited:
			moves.append(a)
	if coordinate[0] < m:
		a = [coordinate[0] + 1, coordinate[1]]
		if grid[coor(a)] != 'X' and a not in visited:
			moves.append(a)
	if coordinate[1] > 1:
		a = [coordinate[0], coordinate[1] - 1]
		if grid[coor(a)] != 'X' and a not in visited:
			moves.append(a)
	if coordinate[1] < n:
		a = [coordinate[0], coordinate[1] + 1]
		if grid[coor(a)] != 'X' and a not in visited:
			moves.append(a)
	if len(moves) > 1:
		for i in moves:
			a = search(i, wand + 1)
			if a != 'T':
				break
		else:
			return 'T'
	else:
		for i in moves:
			a = search(i, wand)
			if a != 'T':
				break
		else:
			return 'T'
	return a
for _ in range(int(input())):
	visited = []
	(n, m) = map(int, input().split())
	coor = lambda a: (a[1] - 1) * m + a[0] - 1
	rev = lambda val: [val % m + 1, int(val / m) + 1]
	grid = ''
	for i in range(n):
		grid += input()
	start = rev(grid.index('M'))
	if search(start) == int(input()):
		print('Impressed')
	else:
		print('Oops!')


from queue import Queue
T = int(input())
for t in range(T):
	[N, M] = list(map(int, input().split(' ')))
	graph = []
	loc_star = (0, 0)
	loc_M = (0, 0)
	find_star = True
	find_M = True
	for i in range(N):
		graph.append([c for c in input()])
		if find_star:
			if '*' in graph[-1]:
				loc_star = (len(graph) - 1, graph[-1].index('*'))
				find_star = False
		if find_M:
			if 'M' in graph[-1]:
				loc_M = (len(graph) - 1, graph[-1].index('M'))
				find_M = False
	frontier = Queue()
	frontier.put(loc_M)
	came_from = {}
	came_from[loc_M] = None
	while not frontier.empty():
		current = frontier.get()
		if current == loc_star:
			break
		(x, y) = current
		neighbors = [coordinate for coordinate in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] if coordinate[0] >= 0 and coordinate[0] < N and (coordinate[1] >= 0) and (coordinate[1] < M) and (graph[coordinate[0]][coordinate[1]] != 'X')]
		for next_loc in neighbors:
			if next_loc not in came_from:
				frontier.put(next_loc)
				came_from[next_loc] = current
	counter = 0
	current = came_from[current]
	while current != None:
		(x, y) = current
		neighbors = [coordinate for coordinate in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] if coordinate[0] >= 0 and coordinate[0] < N and (coordinate[1] >= 0) and (coordinate[1] < M) and (graph[coordinate[0]][coordinate[1]] != 'X')]
		if (current == loc_star or current == loc_M) and len(neighbors) > 1 or len(neighbors) > 2:
			counter += 1
		current = came_from[current]
	K = int(input())
	if counter == K:
		print('Impressed')
	else:
		print('Oops!')


def prepare_state(forest, n, m):

	def is_path_cell(cell):
		return cell in ('.', '*', 'M')
	adj_matrix = [[0] * n * m for _ in range(n * m)]
	(germ_pos, exit_pos) = (None, None)
	for i in range(n):
		for j in range(m):
			if not is_path_cell(forest[i][j]):
				continue
			if '*' == forest[i][j]:
				exit_pos = (i, j)
			if 'M' == forest[i][j]:
				germ_pos = (i, j)
			v1 = i * m + j
			if j + 1 < m and is_path_cell(forest[i][j + 1]):
				v2 = i * m + j + 1
				adj_matrix[v1][v2] = adj_matrix[v2][v1] = 1
			if i + 1 < n and is_path_cell(forest[i + 1][j]):
				v2 = (i + 1) * m + j
				adj_matrix[v1][v2] = adj_matrix[v2][v1] = 1
	return {'adj_matrix': adj_matrix, 'germ_pos': germ_pos, 'exit_pos': exit_pos}

def solve(state, m):
	germ_vertex = state['germ_pos'][0] * m + state['germ_pos'][1]
	exit_vertex = state['exit_pos'][0] * m + state['exit_pos'][1]
	path = []
	path_map = {}

	def find_path(adj_matrix, from_vertex, to_vertex):
		path.append(from_vertex)
		path_map[from_vertex] = True
		if path[len(path) - 1] == to_vertex:
			return True
		for (i, cell) in enumerate(adj_matrix[from_vertex]):
			if 1 == cell and (not path_map.get(i)):
				if find_path(adj_matrix, i, to_vertex):
					return True
		path.pop()
		del path_map[from_vertex]
		return False
	find_path(state['adj_matrix'], germ_vertex, exit_vertex)
	k = 0
	for v in path:
		if exit_vertex != v and 0 < sum([cell for (i, cell) in enumerate(state['adj_matrix'][v]) if not path_map.get(i)]):
			k += 1
	return k
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	state = prepare_state([input() for __ in range(n)], n, m)
	print('Impressed' if int(input()) == solve(state, m) else 'Oops!')


import sys, pdb
mov2camefrom = {'l': 'r', 'r': 'l', 'u': 'd', 'd': 'u'}

def validpos(pos, mat, n, m):
	return 0 <= pos[0] < n and 0 <= pos[1] < m and (mat[pos[0]][pos[1]] != 'X')

def cal4pos(pos):
	return {'l': [pos[0], pos[1] - 1], 'r': [pos[0], pos[1] + 1], 'u': [pos[0] - 1, pos[1]], 'd': [pos[0] + 1, pos[1]]}

def findpath(pos, mat, n, m):

	def fp_rec(pos, mat, mov, movs):
		new_pos = cal4pos(pos)[mov]
		if not validpos(new_pos, mat, n, m):
			return []
		movs.append([pos, mov])
		if mat[new_pos[0]][new_pos[1]] == '*':
			return movs
		next_movs = cal4pos(new_pos)
		next_movs.pop(mov2camefrom[mov])
		for next_mov in next_movs:
			path = fp_rec(new_pos, mat, next_mov, movs)
			if path:
				return path
		movs.pop()
		return []
	movs = ['l', 'r', 'u', 'd']
	for mov in movs:
		path = fp_rec(pos, mat, mov, list())
		if path:
			return path

def starting_pos(mat, n, m):
	for i in range(n):
		for j in range(m):
			if mat[i][j] == 'M':
				return [i, j]

def multiplePaths(pos, camefrom, mat, n, m):
	next_movs = cal4pos(pos)
	if camefrom:
		next_movs.pop(camefrom)
	pathcount = 0
	for mov in next_movs:
		next_pos = next_movs[mov]
		if validpos(next_pos, mat, n, m):
			pathcount += 1
	return pathcount > 1

def exitForest(start, mat, n, m, path):
	wwand = 0
	camefrom = None
	for posmov in path:
		if multiplePaths(posmov[0], camefrom, mat, n, m):
			wwand += 1
		camefrom = mov2camefrom[posmov[1]]
	return wwand
t = int(sys.stdin.readline())
while t > 0:
	t -= 1
	line = sys.stdin.readline().split(' ')
	n = int(line[0])
	m = int(line[1])
	mat = list()
	for i in range(n):
		mat.append(sys.stdin.readline())
	k = int(sys.stdin.readline())
	start = starting_pos(mat, n, m)
	path = findpath(start, mat, n, m)
	if exitForest(start, mat, n, m, path) == k:
		print('Impressed')
	else:
		print('Oops!')


testCaseCount = int(input())
for _ in range(testCaseCount):
	(forestHeight, forestWidth) = [int(x) for x in input().split()]
	forest = {}
	for i in range(forestHeight):
		for (j, char) in enumerate(list(input())):
			forest[i, j] = char
			if char == 'M':
				startingCell = (i, j)
			elif char == '*':
				endingCell = (i, j)
	k = int(input())
	unvisitedCells = [startingCell]
	visitedCells = set()
	predecessors = {}
	choiceCounts = {}
	while unvisitedCells:
		cell = unvisitedCells.pop()
		adjacentCells = [(cell[0] - 1, cell[1]), (cell[0] + 1, cell[1]), (cell[0], cell[1] - 1), (cell[0], cell[1] + 1)]
		neighbors = [c for c in adjacentCells if forest.get(c) in ['.', '*']]
		unvisitedNeighbors = [n for n in neighbors if n not in visitedCells]
		unvisitedCells.extend(unvisitedNeighbors)
		choiceCounts[cell] = len(unvisitedNeighbors)
		for n in neighbors:
			predecessors.setdefault(n, cell)
		visitedCells.add(cell)
		if cell == endingCell:
			break
	wandWaveCount = 0
	cell = endingCell
	while cell != startingCell:
		cell = predecessors[cell]
		if choiceCounts[cell] > 1:
			wandWaveCount += 1
	print('Impressed' if wandWaveCount == k else 'Oops!')


from collections import namedtuple
EMPTY = '.'
TREE = 'X'
START = 'M'
EXIT = '*'
Cell = namedtuple('Cell', ['row', 'col'])

class Grid:

	def __init__(self, matrix):
		self.matrix = matrix
		self.rows = len(self.matrix)
		self.cols = len(self.matrix[0]) if self.matrix else 0

	def tot_num_of_splits(self):
		start = self.find_start()
		return self.num_of_splits(start, None)

	def num_of_splits(self, cell, prev):
		if self[cell] == EXIT:
			return 0
		nbrs = [n for n in self.neighbor_paths(cell) if n != prev]
		current_split = 1 if len(nbrs) > 1 else 0
		for nbr in nbrs:
			n = self.num_of_splits(nbr, cell)
			if n is not None:
				return n + current_split
		return None

	def find_start(self):
		for row in range(0, self.rows):
			for col in range(0, self.cols):
				cell = Cell(row, col)
				if self[cell] == START:
					return cell
		assert False

	def neighbor_paths(self, cell):
		return [n for n in self.neighbors(cell) if self[n] != TREE]

	def neighbors(self, cell):
		(row, col) = (cell.row, cell.col)
		neighbor_cells = (Cell(row - 1, col), Cell(row + 1, col), Cell(row, col - 1), Cell(row, col + 1))
		return filter(self.is_valid, neighbor_cells)

	def is_valid(self, cell):
		(row, col) = (cell.row, cell.col)
		return row >= 0 and col >= 0 and (row < self.rows) and (col < self.cols)

	def __getitem__(self, cell):
		return self.matrix[cell.row][cell.col]
for _ in range(int(input())):
	(rows, cols) = map(int, input().split())
	matrix = []
	for _ in range(rows):
		matrix.append(list(input()))
	k = int(input())
	if Grid(matrix).tot_num_of_splits() == k:
		print('Impressed')
	else:
		print('Oops!')


def main():
	ncases = int(input())
	for case in range(ncases):
		(rows, cols) = map(int, input().split())
		maze = [input() for _ in range(rows)]
		assert all((len(row) == cols for row in maze))
		guess = int(input())
		print('Impressed' if guess == countwaves(maze) else 'Oops!')

def countwaves(maze):
	maze = ['X' + row + 'X' for row in maze]
	sentinelrow = ['X' * len(maze[0])]
	maze = sentinelrow + maze + sentinelrow
	(start, goal) = (locchar('M', maze), locchar('*', maze))
	diff = [(0, 1), (1, 0), (0, -1), (-1, 0)]

	def countrec(prev, current):
		if current == goal:
			return 0
		nextlst = [(current[0] + dx, current[1] + dy) for (dx, dy) in diff]
		nextlst = [nxt for nxt in nextlst if nxt != prev and maze[nxt[0]][nxt[1]] != 'X']
		for nxt in nextlst:
			cnt = countrec(current, nxt)
			if cnt is not None:
				return cnt + (1 if len(nextlst) > 1 else 0)
		return None
	return countrec((None, None), start)

def locchar(char, maze):
	for (irow, row) in enumerate(maze):
		icol = row.find(char)
		if icol != -1:
			return (irow, icol)
	return None
main()


def find_start_end(field, n, m):
	for row_idx in range(n):
		for col_idx in range(m):
			if field[row_idx][col_idx] == 'M':
				start = (row_idx, col_idx)
			if field[row_idx][col_idx] == '*':
				end = (row_idx, col_idx)
	return (start, end)

def move(start, end, field, n, m, parent_nodes, child_nodes):
	children = list()
	for modifier in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		row = start[0] + modifier[0]
		col = start[1] + modifier[1]
		if row < n and row >= 0 and (col < m) and (col >= 0):
			if (field[row][col] == '.' or field[row][col] == '*') and (row, col) not in child_nodes:
				children.append((row, col))
				child_nodes[row, col] = start
	parent_nodes[start] = children
	if end not in children:
		for start in children:
			move(start, end, field, n, m, parent_nodes, child_nodes)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	field = list()
	for _ in range(n):
		field.append([x for x in input()])
	k = int(input())
	(start, end) = find_start_end(field, n, m)
	parent_nodes = dict()
	child_nodes = dict()
	move(start, end, field, n, m, parent_nodes, child_nodes)
	count_cross = 0
	while end != start:
		end = child_nodes[end]
		if len(parent_nodes[end]) > 1:
			count_cross += 1
	if count_cross == k:
		print('Impressed')
	else:
		print('Oops!')


global rows, columns, waves

def search(x, y, grid):
	if grid[x][y] == '*':
		return True
	grid[x][y] = 3
	paths = 0
	search_list = []
	if x < rows - 1:
		if grid[x + 1][y] != 'X' and grid[x + 1][y] != 3:
			search_list.append([x + 1, y])
			paths += 1
	if x > 0:
		if grid[x - 1][y] != 'X' and grid[x - 1][y] != 3:
			search_list.append([x - 1, y])
			paths += 1
	if y < columns - 1:
		if grid[x][y + 1] != 'X' and grid[x][y + 1] != 3:
			search_list.append([x, y + 1])
			paths += 1
	if y > 0:
		if grid[x][y - 1] != 'X' and grid[x][y - 1] != 3:
			search_list.append([x, y - 1])
			paths += 1
	if paths == 0:
		waves.pop()
		return False
	elif paths == 1:
		return search(search_list[0][0], search_list[0][1], grid)
	else:
		ret = False
		for path in search_list:
			waves.append(1)
			ret |= search(path[0], path[1], grid)
		if ret == False:
			waves.pop()
		return ret
testcases = int(input())
for test in range(testcases):
	global rows, columns, waves
	(rows, columns) = [int(i) for i in input().split()]
	hermione = []
	forest = []
	waves = []
	for i in range(rows):
		temp = input()
		forest.append([str(i) for i in temp])
		if 'M' in forest[i]:
			hermione.append(i)
			hermione.append(forest[i].index('M'))
	wave = int(input())
	search(hermione[0], hermione[1], forest)
	if len(waves) == wave:
		print('Impressed')
	else:
		print('Oops!')


from collections import deque
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	b = []
	for i in range(n):
		b.append(input())
	k = int(input())
	d = []
	for i in range(n):
		dl = []
		for j in range(m):
			if b[i][j] == 'X':
				dl.append(-1)
			elif b[i][j] == 'M':
				dl.append(0)
				(sx, sy) = (i, j)
			else:
				dl.append(n * m + 1)
				if b[i][j] == '*':
					(tx, ty) = (i, j)
		d.append(dl)
	q = deque()
	q.append((sx, sy))
	pre = dict()
	while len(q) > 0 and d[tx][ty] > n * m:
		(x, y) = q.popleft()
		dx = d[x][y]
		for (mx, my) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			if x + mx >= 0 and x + mx < n and (y + my >= 0) and (y + my < m) and (d[x + mx][y + my] > n * m):
				d[x + mx][y + my] = dx + 1
				pre[x + mx, y + my] = (x, y)
				q.append((x + mx, y + my))
	(x, y, c) = (tx, ty, 0)
	while (x, y) != (sx, sy):
		(x, y) = pre[x, y]
		deg = 0
		for (mx, my) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
			if x + mx >= 0 and x + mx < n and (y + my >= 0) and (y + my < m) and (b[x + mx][y + my] != 'X'):
				deg += 1
		if x == sx and y == sy and (deg >= 2) or deg > 2:
			c += 1
	print('Impressed' if c == k else 'Oops!')


def get_valid_neighbors(point, grid, n, m):
	neighbors = []
	if point[0] != 0 and grid[point[0] - 1][point[1]] != 'X':
		neighbors.append((point[0] - 1, point[1]))
	if point[0] != n - 1 and grid[point[0] + 1][point[1]] != 'X':
		neighbors.append((point[0] + 1, point[1]))
	if point[1] != 0 and grid[point[0]][point[1] - 1] != 'X':
		neighbors.append((point[0], point[1] - 1))
	if point[1] != m - 1 and grid[point[0]][point[1] + 1] != 'X':
		neighbors.append((point[0], point[1] + 1))
	return neighbors

def find_exit_with_branch_count(point, grid, n, m, visited, count):
	my_count = count
	possible_paths = get_valid_neighbors(point, grid, n, m)
	children = [x for x in possible_paths if x not in visited]
	if len(children) == 0:
		return (False, 0)
	for child in children:
		visited.add(child)
	if len(children) > 1:
		my_count += 1
	if len([x for x in children if grid[x[0]][x[1]] == '*']) > 0:
		return (True, my_count)
	for child in children:
		result = find_exit_with_branch_count(child, grid, n, m, visited, my_count)
		if result[0]:
			return result
	return (False, 0)
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	grid = []
	root = None
	for y in range(n):
		grid.append(list(input()))
		if not root and 'M' in grid[-1]:
			x = grid[-1].index('M')
			root = (y, x)
	visited = set()
	visited.add(root)
	result = find_exit_with_branch_count(root, grid, n, m, visited, 0)
	num = int(input())
	if result[1] == num:
		print('Impressed')
	else:
		print('Oops!')


from collections import deque
from collections import namedtuple
import time
cases = []
Case = namedtuple('Case', ['N', 'M', 'map', 'K'])
for _ in range(int(input())):
	(N, M) = [int(i) for i in input().split()]
	map = [input() for _ in range(N)]
	K = int(input())
	cases.append(Case(N, M, map, K))
Index = namedtuple('Index', ['i', 'j'])
State = namedtuple('State', ['index', 'K', 'prev'])

def find_char(case, char):
	for i in range(case.N):
		for j in range(case.M):
			if case.map[i][j] == char:
				return Index(i, j)
	return None
for case in cases:
	start_idx = find_char(case, 'M')
	end_idx = find_char(case, '*')
	states = deque()
	current_state = State(start_idx, 0, None)
	while current_state.index != end_idx:
		next_list = []
		if current_state.index.i > 0:
			next_list.append(Index(current_state.index.i - 1, current_state.index.j))
		if current_state.index.j > 0:
			next_list.append(Index(current_state.index.i, current_state.index.j - 1))
		if current_state.index.i < case.N - 1:
			next_list.append(Index(current_state.index.i + 1, current_state.index.j))
		if current_state.index.j < case.M - 1:
			next_list.append(Index(current_state.index.i, current_state.index.j + 1))
		next_list = [idx for idx in next_list if case.map[idx.i][idx.j] != 'X']
		next_list = [idx for idx in next_list if current_state.prev == None or not (idx.i == current_state.prev.index.i and idx.j == current_state.prev.index.j)]
		new_k = current_state.K
		if len(next_list) > 1:
			new_k += 1
		for idx in next_list:
			states.append(State(idx, new_k, current_state))
		current_state = states.popleft()
	if current_state.K == case.K:
		print('Impressed')
	else:
		print('Oops!')


def search(grid, oR, oc, r, c):
	if grid[r][c] == '*':
		return 0
	paths = []
	dels = ((-1, 0), (1, 0), (0, -1), (0, 1))
	for (dr, dc) in dels:
		nr = r + dr
		nc = c + dc
		if nr >= 0 and nr < len(grid) and (nc >= 0) and (nc < len(grid[0])):
			if nr != oR or nc != oc:
				if grid[nr][nc] in ('*', '.'):
					paths.append((nr, nc))
	if len(paths) == 0:
		return -1
	elif len(paths) == 1:
		(nr, nc) = paths[0]
		return search(grid, r, c, nr, nc)
	else:
		for (nr, nc) in paths:
			ns = search(grid, r, c, nr, nc)
			if ns >= 0:
				return 1 + ns
		return -1
t = int(input())
for ti in range(t):
	(rows, cols) = map(int, input().split(' '))
	grid = []
	(sr, sc) = (0, 0)
	for r in range(rows):
		grid.append(input())
		i = grid[-1].find('M')
		if i >= 0:
			sr = r
			sc = i
	k = int(input())
	w = search(grid, sr, sc, sr, sc)
	if w == k:
		print('Impressed')
	else:
		print('Oops!')


import sys

def find_point(grids, p):
	for i in range(len(grids)):
		for j in range(len(grids[0])):
			if grids[i][j] == p:
				return (i, j)

def need_wave_wand(grids, point, start_point):
	(px, py) = point
	count = 0
	if px - 1 >= 0 and grids[px - 1][py] != 'X':
		count += 1
	if px + 1 < len(grids) and grids[px + 1][py] != 'X':
		count += 1
	if py - 1 >= 0 and grids[px][py - 1] != 'X':
		count += 1
	if py + 1 < len(grids[0]) and grids[px][py + 1] != 'X':
		count += 1
	if start_point:
		return count >= 2
	else:
		return count >= 3

def backtrace_path(queue, ptr):
	output = []
	while ptr >= 0:
		(x, y, p) = queue[ptr]
		ptr = p
		output.insert(0, (x, y))
	return output

def find_path(grids, ep, hp):
	(ex, ey) = ep
	(hx, hy) = hp
	visited_set = set()
	queue = []
	visited_set.add((hx, hy))
	queue.append((hx, hy, -1))
	head = 0
	while True:
		(cx, cy, cp) = queue[head]
		for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			(nx, ny) = (cx + dx, cy + dy)
			if (nx, ny) not in visited_set and 0 <= nx < len(grids) and (0 <= ny < len(grids[0])) and (grids[nx][ny] != 'X'):
				queue.append((nx, ny, head))
				visited_set.add((nx, ny))
				if nx == ex and ny == ey:
					return backtrace_path(queue, len(queue) - 1)
		head += 1

def count_luck():
	(N, M) = [int(x) for x in sys.stdin.readline().split()]
	grids = []
	for _ in range(N):
		grids.append(sys.stdin.readline().strip())
	K = int(sys.stdin.readline())
	exit_point = find_point(grids, '*')
	hermione_point = find_point(grids, 'M')
	path = find_path(grids, exit_point, hermione_point)
	count = 0
	for (i, point) in enumerate(path[:-1]):
		if need_wave_wand(grids, point, i == 0):
			count += 1
	if count == K:
		print('Impressed')
	else:
		print('Oops!')
T = int(sys.stdin.readline())
for _ in range(T):
	count_luck()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	M = [list('X' * (m + 2))] + [list('X' + input() + 'X') for j in range(n)] + [list('X' * (m + 2))]
	k = int(input())
	(src,) = [(y, x) for y in range(n + 2) for x in range(m + 2) if M[y][x] == 'M']
	(dst,) = [(y, x) for y in range(n + 2) for x in range(m + 2) if M[y][x] == '*']
	M[src[0]][src[1]] = '.'
	M[dst[0]][dst[1]] = '.'
	q = [(src, 0)]
	while q:
		((y, x), kk) = q.pop()
		if (y, x) == dst:
			print('Impressed' if kk == k else 'Oops!')
			break
		M[y][x] = 'X'
		r = []
		for pos in [(y, x - 1), (y, x + 1), (y - 1, x), (y + 1, x)]:
			if M[pos[0]][pos[1]] == '.':
				r.append(pos)
		if len(r) > 1:
			kk += 1
		for pos in r:
			q.append((pos, kk))


from collections import deque

class Movement:
	STATIC = 0
	UP = 1
	RIGHT = 2
	DOWN = 3
	LEFT = 4

def desc_movement(movement):
	if movement == Movement.STATIC:
		return 'static'
	elif movement == Movement.UP:
		return 'up'
	elif movement == Movement.RIGHT:
		return 'right'
	elif movement == Movement.DOWN:
		return 'down'
	elif movement == Movement.LEFT:
		return 'left'

class Grid:

	def __init__(self, n, m):
		self.grid = []
		self.n = n
		self.m = m

	def at(self, pos):
		(i, j) = pos
		return self.grid[i][j]

	def fpos(self, c):
		pos = None
		for i in range(self.n):
			for j in range(self.m):
				if self.grid[i][j].c == c:
					pos = (i, j)
					break
		return pos

class Node:

	def __init__(self, grid, c, pos):
		self.visited = False
		self.grid = grid
		self.c = c
		self.pos = pos
		self.u = 0
		self.movement = Movement.STATIC
		self.before = None

	def chmovement(self, movement):
		self.movement = movement
		return self

	def chbefore(self, before):
		self.before = before
		return self

	def chu(self, u):
		self.u = u
		return self

	def moveok(self, npos):
		if self.grid.at(npos).c == 'X':
			return None
		else:
			return self.grid.at(npos)

	def up(self):
		(i, j) = self.pos
		if i != 0:
			npos = (i - 1, j)
			return self.moveok(npos)
		else:
			return None

	def right(self):
		(i, j) = self.pos
		if j != self.grid.m - 1:
			npos = (i, j + 1)
			return self.moveok(npos)
		else:
			return None

	def down(self):
		(i, j) = self.pos
		if i != self.grid.n - 1:
			npos = (i + 1, j)
			return self.moveok(npos)
		else:
			return None

	def left(self):
		(i, j) = self.pos
		if j != 0:
			npos = (i, j - 1)
			return self.moveok(npos)
		else:
			return None

	def __repr__(self):
		return self.c

def uvisit(cg):
	u = 0
	if cg.up() != None and (not cg.up().visited):
		u += 1
	if cg.right() != None and (not cg.right().visited):
		u += 1
	if cg.down() != None and (not cg.down().visited):
		u += 1
	if cg.left() != None and (not cg.left().visited):
		u += 1
	return u

def rmain():
	(n, m) = map(int, input().split(' '))
	grid = Grid(n, m)
	for i in range(n):
		grid.grid.append([Node(grid, c, (i, j)) for (j, c) in enumerate(input())])
	k = int(input())
	startpos = grid.fpos('M')
	finishpos = grid.fpos('*')
	fg = grid.at(finishpos)
	q = deque()
	q.append(grid.at(startpos))
	l = 0
	while len(q) > 0:
		cg = q.popleft()
		cg.visited = True
		if cg == fg:
			break
		u = uvisit(cg)
		if cg.up() != None and (not cg.up().visited):
			q.append(cg.up().chbefore(cg).chmovement(Movement.UP).chu(u))
		if cg.right() != None and (not cg.right().visited):
			q.append(cg.right().chbefore(cg).chmovement(Movement.RIGHT).chu(u))
		if cg.down() != None and (not cg.down().visited):
			q.append(cg.down().chbefore(cg).chmovement(Movement.DOWN).chu(u))
		if cg.left() != None and (not cg.left().visited):
			q.append(cg.left().chbefore(cg).chmovement(Movement.LEFT).chu(u))
	l = 0
	cg = fg
	while cg.before != None:
		if cg.u > 1:
			l += 1
		cg = cg.before
	print((lambda l: 'Impressed' if l == k else 'Oops!')(l))
ncase = int(input())
for i in range(ncase):
	rmain()


def waves(forest, s):
	(i, j) = s
	waves = {(i, j): 0}
	forest[i][j] = 0
	vs = [s]
	while True:
		(i, j) = vs.pop()
		d = forest[i][j]
		neighbours = []
		for (i2, j2) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
			if 0 <= i2 < n and 0 <= j2 < m and (forest[i2][j2] in ['.', '*']):
				neighbours.append((i2, j2))
		for (i2, j2) in neighbours:
			if forest[i2][j2] == '.':
				forest[i2][j2] = d + 1
				waves[i2, j2] = waves[i, j] + (1 if len(neighbours) > 1 else 0)
			elif forest[i2][j2] == '*':
				return waves[i, j] + (1 if len(neighbours) > 1 else 0)
		vs.extend(neighbours)
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	forest = []
	(s, t) = (None, None)
	for i in range(n):
		forest_row = []
		for (j, c) in enumerate(input()):
			if c == 'M':
				s = (i, j)
			elif c == '*':
				t = (i, j)
			forest_row.append(c)
		forest.append(forest_row)
	k = int(input())
	if k == waves(forest, s):
		print('Impressed')
	else:
		print('Oops!')


def findk(world, ktarget):
	itarget = -1
	iherm = -1
	for (i, row) in enumerate(world):
		try:
			jtarget = row.index('*')
			itarget = i
		except ValueError:
			pass
		try:
			jherm = row.index('M')
			iherm = i
		except ValueError:
			pass
		if itarget >= 0 and iherm >= 0:
			break
	world[itarget][jtarget] = '.'
	world[iherm][jherm] = '.'
	paths = [(iherm, jherm, ktarget)]
	while paths:
		npaths = []
		for (i, j, k) in paths:
			if world[i][j] != '.' or k < 0:
				continue
			if i == itarget and j == jtarget:
				return k
			world[i][j] = 'M'
			npos = []
			if i > 0 and world[i - 1][j] == '.':
				npos.append((i - 1, j))
			if j > 0 and world[i][j - 1] == '.':
				npos.append((i, j - 1))
			if i < n - 1 and world[i + 1][j] == '.':
				npos.append((i + 1, j))
			if j < m - 1 and world[i][j + 1] == '.':
				npos.append((i, j + 1))
			nk = k if len(npos) == 1 else k - 1
			for (ni, nj) in npos:
				npaths.append((ni, nj, nk))
		paths = npaths
	return -1
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	world = []
	for i in range(n):
		world.append(list(input().strip()))
	ktarget = int(input())
	print('Impressed' if findk(world, ktarget) == 0 else 'Oops!')


def search(mp, mx, my, px, py, m, n):
	left = 'B'
	right = 'B'
	top = 'B'
	bottom = 'B'
	if mx - 1 >= 0 and (mx - 1 != px or my != py):
		left = mp[my][mx - 1]
	if my + 1 < n and (mx != px or my + 1 != py):
		bottom = mp[my + 1][mx]
	if mx + 1 < m and (mx + 1 != px or my != py):
		right = mp[my][mx + 1]
	if my - 1 >= 0 and (mx != px or my - 1 != py):
		top = mp[my - 1][mx]
	if mp[my][mx] == '*':
		return (1, 0)
	if (left == 'B' or left == 'X') and (right == 'B' or right == 'X') and (top == 'B' or top == 'X') and (bottom == 'B' or bottom == 'X'):
		return (0, 0)
	else:
		paths = 0
		illuminate = 0
		exit = 0
		if left == '*' or top == '*' or right == '*' or (bottom == '*'):
			if left == '.':
				paths += 1
			if top == '.':
				paths += 1
			if right == '.':
				paths += 1
			if bottom == '.':
				paths += 1
			if left == '*':
				paths += 1
				(tmp1, tmp2) = search(mp, mx - 1, my, mx, my, m, n)
				if exit != 1 and tmp1 == 1:
					exit = tmp1
				if tmp1 == 1:
					illuminate = tmp2
			if top == '*':
				paths += 1
				(tmp1, tmp2) = search(mp, mx, my - 1, mx, my, m, n)
				if exit != 1 and tmp1 == 1:
					exit = tmp1
				if tmp1 == 1:
					illuminate = tmp2
			if right == '*':
				paths += 1
				(tmp1, tmp2) = search(mp, mx + 1, my, mx, my, m, n)
				if exit != 1 and tmp1 == 1:
					exit = tmp1
				if tmp1 == 1:
					illuminate = tmp2
			if bottom == '*':
				paths += 1
				(tmp1, tmp2) = search(mp, mx, my + 1, mx, my, m, n)
				if exit != 1 and tmp1 == 1:
					exit = tmp1
				if tmp1 == 1:
					illuminate = tmp2
		else:
			if left == '.':
				paths += 1
				(tmp1, tmp2) = search(mp, mx - 1, my, mx, my, m, n)
				if exit != 1 and tmp1 == 1:
					exit = tmp1
				if tmp1 == 1:
					illuminate = tmp2
			if top == '.':
				paths += 1
				(tmp1, tmp2) = search(mp, mx, my - 1, mx, my, m, n)
				if exit != 1 and tmp1 == 1:
					exit = tmp1
				if tmp1 == 1:
					illuminate = tmp2
			if right == '.':
				paths += 1
				(tmp1, tmp2) = search(mp, mx + 1, my, mx, my, m, n)
				if exit != 1 and tmp1 == 1:
					exit = tmp1
				if tmp1 == 1:
					illuminate = tmp2
			if bottom == '.':
				paths += 1
				(tmp1, tmp2) = search(mp, mx, my + 1, mx, my, m, n)
				if exit != 1 and tmp1 == 1:
					exit = tmp1
				if tmp1 == 1:
					illuminate = tmp2
		if paths > 1 and exit == 1:
			illuminate += 1
			return (1, illuminate)
		else:
			return (exit, illuminate)
t = int(input())
while t > 0:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	mp = [[0 for i in range(0, m)] for i in range(0, n)]
	mx = 0
	my = 0
	fx = 0
	fy = 0
	for i in range(0, n):
		tmp = input()
		for j in range(0, m):
			mp[i][j] = tmp[j]
			if tmp[j] == 'M':
				mx = j
				my = i
	(w, illuminate) = search(mp, mx, my, mx, my, m, n)
	k = int(input())
	print('Impressed' if illuminate == k else 'Oops!')
	t -= 1


def bfs(Adj, s):
	level = {s: 0}
	parent = {s: None}
	i = 1
	frontier = [s]
	while frontier:
		next = []
		for u in frontier:
			for v in Adj[u]:
				if v not in level:
					level[v] = i
					parent[v] = u
					next.append(v)
		frontier = next
		i += 1
	return parent
numtest = int(input())
for z in range(numtest):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	l = []
	g = {}
	start = ''
	stop = ''
	for i in range(n):
		l.append(input())
	a = int(input())
	for i in range(n):
		for j in range(m):
			sij = str(i) + '.' + str(j)
			if l[i][j] == '*':
				start = sij
			elif l[i][j] == 'M':
				stop = sij
			if i != 0 and l[i][j] != 'X' and (l[i - 1][j] != 'X'):
				if sij not in g:
					g[sij] = []
				g[sij].append(str(i - 1) + '.' + str(j))
			if j != 0 and l[i][j] != 'X' and (l[i][j - 1] != 'X'):
				if sij not in g:
					g[sij] = []
				g[sij].append(str(i) + '.' + str(j - 1))
			if j != m - 1 and l[i][j] != 'X' and (l[i][j + 1] != 'X'):
				if sij not in g:
					g[sij] = []
				g[sij].append(str(i) + '.' + str(j + 1))
			if i != n - 1 and l[i][j] != 'X' and (l[i + 1][j] != 'X'):
				if sij not in g:
					g[sij] = []
				g[sij].append(str(i + 1) + '.' + str(j))
	parent = bfs(g, start)
	ans = 0
	if len(g[stop]) > 1:
		ans += 1
	tmp = parent[stop]
	while tmp != start:
		if len(g[tmp]) > 2:
			ans += 1
		tmp = parent[tmp]
	if ans == a:
		print('Impressed')
	else:
		print('Oops!')


def find_path(lab):
	start = (0, 0)
	end = (0, 0)
	for i in range(len(lab)):
		for j in range(len(lab[0])):
			if lab[i][j] == '*':
				end = (i, j)
			elif lab[i][j] == 'M':
				start = (i, j)
	return find_rec(lab, start, 0, (-1, -1))

def find_rec(lab, start, L, last):
	dirs = [0, 0, 0, 0]
	symb = lab[start[0]][start[1]]
	if symb == '*':
		return L
	if start[0] > 0 and (start[0] - 1, start[1]) != last:
		if lab[start[0] - 1][start[1]] != 'X':
			dirs[0] = 1
	if start[1] > 0 and (start[0], start[1] - 1) != last:
		if lab[start[0]][start[1] - 1] != 'X':
			dirs[1] = 1
	if start[0] < len(lab) - 1 and (start[0] + 1, start[1]) != last:
		if lab[start[0] + 1][start[1]] != 'X':
			dirs[2] = 1
	if start[1] < len(lab[0]) - 1 and (start[0], start[1] + 1) != last:
		if lab[start[0]][start[1] + 1] != 'X':
			dirs[3] = 1
	if sum(dirs) > 1:
		L += 1
	K = -1
	if dirs[0] == 1:
		p = (start[0] - 1, start[1])
		if p != last:
			K = find_rec(lab, p, L, start)
			if K > -1:
				return K
	if dirs[1] == 1:
		p = (start[0], start[1] - 1)
		if p != last:
			K = find_rec(lab, p, L, start)
			if K > -1:
				return K
	if dirs[2] == 1:
		p = (start[0] + 1, start[1])
		if p != last:
			K = find_rec(lab, p, L, start)
			if K > -1:
				return K
	if dirs[3] == 1:
		p = (start[0], start[1] + 1)
		if p != last:
			K = find_rec(lab, p, L, start)
			if K > -1:
				return K
	return -1
T = int(input())
for i in range(T):
	tmp = input().split()
	N = int(tmp[0])
	M = int(tmp[1])
	labyrinth = []
	for j in range(N):
		tmp = input()
		tmp = [tmp[i] for i in range(len(tmp))]
		labyrinth.append(tmp)
	L = find_path(labyrinth)
	K = int(input())
	if K == L:
		print('Impressed')
	else:
		print('Oops!')


import sys

def getLength():
	return sys.stdin.readline().split()

def getBoard(times):
	board = []
	for x in range(times):
		board.append(list(sys.stdin.readline()))
	return board

def findHermione(board):
	for (row, rData) in enumerate(board):
		try:
			column = rData.index('M')
		except ValueError:
			continue
		return [row, column]
	return -1

def makeMoves(curPos, pastPos=None, waves=0):
	positions.append(curPos)
	moves = []
	y = curPos[0]
	x = curPos[1]
	herms = board[y][x]
	pastY = pastPos[0] if pastPos else curPos[0]
	pastX = pastPos[1] if pastPos else curPos[1]
	for move in range(-1, 2, 2):
		if (x + move in range(0, columns)) & (x + move != pastX):
			if board[y][x + move] == '.' or board[y][x + move] == '*':
				moves.append([y, x + move])
		if (y + move in range(0, rows)) & (y + move != pastY):
			if board[y + move][x] == '.' or board[y + move][x] == '*':
				moves.append([y + move, x])
	checkWin(herms, waves)
	if len(moves) == 0:
		positions.remove(curPos)
	elif len(moves) == 1:
		makeMoves(moves[0], curPos, waves)
	else:
		waves += 1
		for move in moves:
			makeMoves(move, curPos, waves)

def checkWin(herms, waves):
	if herms == '*':
		print('Impressed' if waves == k else 'Oops!')
testCases = int(sys.stdin.readline())
for times in range(0, testCases):
	length = getLength()
	rows = int(length[0])
	columns = int(length[1])
	board = getBoard(rows)
	k = int(sys.stdin.readline())
	positions = []
	makeMoves(findHermione(board))


def find_start(r, c, l):
	for i in range(r):
		for j in range(c):
			if l[i][j] == 'M':
				return (i, j)

def get_neighbors(pos_x, pos_y, cells):
	l = []
	try:
		if pos_y - 1 >= 0:
			a = cells[pos_x][pos_y - 1]
			l.append([cells[pos_x][pos_y - 1], (pos_x, pos_y - 1)])
	except:
		pass
	try:
		if pos_x - 1 >= 0:
			a = cells[pos_x - 1][pos_y]
			l.append([cells[pos_x - 1][pos_y], (pos_x - 1, pos_y)])
	except:
		pass
	try:
		a = cells[pos_x][pos_y + 1]
		l.append([cells[pos_x][pos_y + 1], (pos_x, pos_y + 1)])
	except:
		pass
	try:
		a = cells[pos_x + 1][pos_y]
		l.append([cells[pos_x + 1][pos_y], (pos_x + 1, pos_y)])
	except:
		pass
	return l

def has_exit_neighbor(l):
	for i in l:
		if i[0] == '*':
			return True
	return False

def get_open_neighbors(l):
	o_l = []
	for i in l:
		if i[0] == '.':
			o_l.append(i)
	return o_l

def find_waves(pos_x, pos_y, cells, n_waves):
	l = get_neighbors(pos_x, pos_y, cells)
	o_l = get_open_neighbors(l)
	n_o_l = len(o_l)
	if has_exit_neighbor(l):
		if n_o_l > 0:
			return n_waves + 1
		return n_waves
	cells[pos_x][pos_y] = 'X'
	if n_o_l <= 0:
		return -1
	elif n_o_l == 1:
		return find_waves(o_l[0][1][0], o_l[0][1][1], cells, n_waves)
	else:
		for path in o_l:
			tmp_n_waves = find_waves(path[1][0], path[1][1], cells, n_waves + 1)
			try:
				if tmp_n_waves > 0:
					return tmp_n_waves
			except:
				pass
	return
n_cases = int(input())
for case in range(n_cases):
	[r, c] = [int(a) for a in input().split()]
	cells = []
	for i in range(r):
		cells.append(list(input()))
	(start_x, start_y) = find_start(r, c, cells)
	n_waves_act = find_waves(start_x, start_y, cells, 0)
	n_waves_exp = int(input())
	if n_waves_act == n_waves_exp:
		print('Impressed')
	else:
		print('Oops!')


class Node:

	def __init__(self, x, y, value=None):
		self.x = x
		self.y = y
		self.value = value
		self.adjacents = []
		self.state = 'white'

	def addAdjacent(self, node):
		if node not in self.adjacents:
			self.adjacents.append(node)

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

	def toTuple(self):
		return (self.x, self.y)

	def getAdjacentCoords(self):
		options = []
		coords = [(x, y) for x in range(self.x - 1, self.x + 2) for y in range(self.y - 1, self.y + 2) if x >= 0 and y >= 0 and (x == self.x or y == self.y) and (Node(x, y) != self)]
		return coords

	def __repr__(self):
		return '(%d, %d)' % (self.x, self.y)

def dfs(node, path=[]):
	if len(path) == 0:
		if node.state == 'white':
			node.state = 'grey'
			if node.value == '*':
				path.append(node)
				return
			for n in node.adjacents:
				dfs(n, path)
				if len(path) > 0:
					path.append(node)
					return
t = int(input())
for ti in range(t):
	nodes = {}
	(N, M) = map(int, input().split(' '))
	startPoint = None
	for ni in range(N):
		row = input()
		column = 0
		for c in row:
			if c != 'X':
				currentNode = Node(ni, column, c)
				nodes[ni, column] = currentNode
				if c == 'M':
					startPoint = currentNode
			column += 1
	k = int(input())
	for n in nodes.values():
		for adj in n.getAdjacentCoords():
			if adj in nodes:
				n.addAdjacent(nodes[adj])
				nodes[adj].addAdjacent(n)
	path = []
	dfs(startPoint, path)
	counter = 0
	for n in path:
		if n.value == '.' and len(n.adjacents) > 2 or (n.value == 'M' and len(n.adjacents) > 1):
			counter += 1
	if counter == k:
		output = 'Impressed'
	else:
		output = 'Oops!'
	print(output)


def in_forest(forest, row, col):
	return row >= 0 and row < len(forest) and (col >= 0) and (col < len(forest[0]))

def neighbors(forest, row, col):
	directions = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
	return [x for x in directions if in_forest(forest, *x)]

def legal_moves(forest, visited, row, col):
	directions = neighbors(forest, row, col)
	return [x for x in directions if x not in visited and forest[x[0]][x[1]] != 'X']

def dfs(forest, node, end, visited, luck=0):
	visited.add(node)
	if node == end:
		return (True, luck)
	moves = legal_moves(forest, visited, *node)
	if len(moves) > 1:
		luck += 1
	for move in moves:
		if move not in visited:
			(success, move_luck) = dfs(forest, move, end, visited, luck)
			if success:
				return (True, move_luck)
	return (False, 0)

def solve(forest, start, end, k):
	(success, luck) = dfs(forest, start, end, set())
	if success:
		if luck == k:
			return 'Impressed'
		else:
			return 'Oops!'
	else:
		print('Something is wrong')
for _ in range(int(input())):
	(rows, cols) = [int(x) for x in input().split()]
	forest = [list() for x in range(rows)]
	start = (0, 0)
	end = (0, 0)
	for i in range(rows):
		line = input()
		for j in range(cols):
			forest[i].append(line[j])
			if line[j] == 'M':
				start = (i, j)
			elif line[j] == '*':
				end = (i, j)
	k = int(input())
	print(solve(forest, start, end, k))


def getNbWand(FF):
	(N, M) = (len(FF), len(FF[0]))
	(S, E) = (None, None)
	for x in range(M):
		for y in range(N):
			if FF[y][x] == 'M':
				S = (x, y)
			elif FF[y][x] == '*':
				E = (x, y)
	stack = [(S, 0)]
	while stack:
		(p, c) = stack.pop()
		(x, y) = p
		if p == E:
			return c
		FF[y][x] = 'X'
		v = []
		if x > 0 and FF[y][x - 1] != 'X':
			v.append((x - 1, y))
		if y > 0 and FF[y - 1][x] != 'X':
			v.append((x, y - 1))
		if x < M - 1 and FF[y][x + 1] != 'X':
			v.append((x + 1, y))
		if y < N - 1 and FF[y + 1][x] != 'X':
			v.append((x, y + 1))
		if len(v) > 1:
			c += 1
		for vv in v:
			stack.append((vv, c))
T = int(input())
for _ in range(T):
	(N, M) = (int(_) for _ in input().split())
	FF = [list(input()) for _ in range(N)]
	K = int(input())
	if K == getNbWand(FF):
		print('Impressed')
	else:
		print('Oops!')


t = int(input().strip())
for case in range(0, t):
	(n, m) = list(map(int, input().strip().split()))
	forest = list()
	ystart = 0
	xstart = 0
	for i in range(0, n):
		forest.append(list(input().strip()))
		if 'M' in forest[i]:
			ystart = i
			xstart = forest[i].index('M')
	k = int(input().strip())
	queue = [[ystart, xstart, 'NA', 0]]
	while True:
		(y, x, direction, count) = queue[0]
		temp_queue = []
		exit = False
		if direction != 'UP' and y < n - 1 and (forest[y + 1][x] != 'X'):
			if forest[y + 1][x] == '*':
				exit = True
			temp_queue.append([y + 1, x, 'DOWN'])
		if direction != 'RIGHT' and x > 0 and (forest[y][x - 1] != 'X'):
			if forest[y][x - 1] == '*':
				exit = True
			temp_queue.append([y, x - 1, 'LEFT'])
		if direction != 'DOWN' and y > 0 and (forest[y - 1][x] != 'X'):
			if forest[y - 1][x] == '*':
				exit = True
			temp_queue.append([y - 1, x, 'UP'])
		if direction != 'LEFT' and x < m - 1 and (forest[y][x + 1] != 'X'):
			if forest[y][x + 1] == '*':
				exit = True
			temp_queue.append([y, x + 1, 'RIGHT'])
		del queue[0]
		if len(temp_queue) > 1:
			count += 1
		if exit:
			if count == k:
				print('Impressed')
			else:
				print('Oops!')
			break
		for item in temp_queue:
			item.append(count)
			queue.append(item)


def find_source(grid):
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] == 'M':
				return (i, j)
	return (-1, -1)

def need_wave(grid, r, c, least_choices):
	(m, n) = (len(grid), len(grid[0]))
	num_choices = 0
	for (r, c) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
		if 0 <= r < m and 0 <= c < n and (grid[r][c] != 'X'):
			num_choices += 1
	return num_choices >= least_choices

def search(grid, k):
	(m, n) = (len(grid), len(grid[0]))
	(r, c) = find_source(grid)
	visited = [[False] * n for _ in range(m)]
	stack = [(r, c)]
	visited[r][c] = True
	while stack:
		(r, c) = stack[-1]
		if grid[r][c] == '*':
			stack.pop()
			break
		elif r - 1 >= 0 and (not visited[r - 1][c]) and (grid[r - 1][c] != 'X'):
			stack.append((r - 1, c))
			visited[r - 1][c] = True
		elif c + 1 < n and (not visited[r][c + 1]) and (grid[r][c + 1] != 'X'):
			stack.append((r, c + 1))
			visited[r][c + 1] = True
		elif r + 1 < m and (not visited[r + 1][c]) and (grid[r + 1][c] != 'X'):
			stack.append((r + 1, c))
			visited[r + 1][c] = True
		elif c - 1 >= 0 and (not visited[r][c - 1]) and (grid[r][c - 1] != 'X'):
			stack.append((r, c - 1))
			visited[r][c - 1] = True
		else:
			stack.pop()
	total_waves = 0
	for (r, c) in stack[1:]:
		if need_wave(grid, r, c, 3):
			total_waves += 1
	(r, c) = stack[0]
	if need_wave(grid, r, c, 2):
		total_waves += 1
	return total_waves == k

def main():
	T = int(input())
	for _ in range(T):
		(n, m) = [int(s) for s in input().split()]
		grid = [input() for _ in range(n)]
		k = int(input())
		print('Impressed' if search(grid, k) else 'Oops!')
main()


from collections import deque

def traverse_forest(N, M, F):
	V = [[False for _ in range(M)] for _ in range(N)]
	B = [[None for _ in range(M)] for _ in range(N)]
	start = None
	finish = None
	for i in range(N):
		for j in range(M):
			if F[i][j] == 'M':
				start = (i, j)
			if F[i][j] == '*':
				finish = (i, j)
	P = [finish]
	Q = deque([start])
	while Q and finish not in Q:
		p = Q.popleft()
		for offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			q = (p[0] + offset[0], p[1] + offset[1])
			if 0 <= q[0] <= N - 1 and 0 <= q[1] <= M - 1 and (not V[q[0]][q[1]]):
				if F[q[0]][q[1]] != 'X':
					V[q[0]][q[1]] = True
					B[q[0]][q[1]] = p
					Q.append(q)
	while P[-1] != start:
		c = P[-1]
		P.append(B[c[0]][c[1]])
	P = P[::-1]
	V = [[False for _ in range(M)] for _ in range(N)]
	wand = 0
	for p in P[:-1]:
		count = 0
		V[p[0]][p[1]] = True
		for offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			q = (p[0] + offset[0], p[1] + offset[1])
			if 0 <= q[0] <= N - 1 and 0 <= q[1] <= M - 1 and (not V[q[0]][q[1]]):
				if F[q[0]][q[1]] != 'X':
					count += 1
		if count > 1:
			wand += 1
	return wand

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = [int(i) for i in input().split()]
		F = [[c for c in input()] for _ in range(N)]
		K = int(input())
		print('Impressed' if traverse_forest(N, M, F) == K else 'Oops!')
main()


t = int(input())
for x in range(0, t):
	line = input().split(' ')
	n = int(line[0])
	m = int(line[1])
	forest = []
	for i in range(0, n):
		forest.append(input())
	k = int(input())
	start = ()
	end = ()
	for i in range(0, n):
		for j in range(0, m):
			if forest[i][j] == 'M':
				start = (i, j)
			if forest[i][j] == '*':
				end = (i, j)
	path = [start]
	checked = []
	superpath = [[()] * m for x in range(0, n)]
	superpath[start[0]][start[1]] = (-1, -1)
	wands = 0
	while len(path) != 0:
		temp = path.pop()
		superpath.append(temp)
		if temp == end:
			break
		i = temp[0]
		j = temp[1]
		checked.append(temp)
		if i + 1 < n:
			if forest[i + 1][j] != 'X':
				if not (i + 1, j) in checked:
					path.append((i + 1, j))
					superpath[i + 1][j] = temp
		if i - 1 >= 0:
			if forest[i - 1][j] != 'X':
				if not (i - 1, j) in checked:
					path.append((i - 1, j))
					superpath[i - 1][j] = temp
		if j + 1 < m:
			if forest[i][j + 1] != 'X':
				if not (i, j + 1) in checked:
					path.append((i, j + 1))
					superpath[i][j + 1] = temp
		if j - 1 >= 0:
			if forest[i][j - 1] != 'X':
				if not (i, j - 1) in checked:
					path.append((i, j - 1))
					superpath[i][j - 1] = temp
	p = superpath[end[0]][end[1]]
	while p != (-1, -1):
		i = p[0]
		j = p[1]
		ways = 0
		if i + 1 < n:
			if forest[i + 1][j] != 'X':
				ways += 1
		if i - 1 >= 0:
			if forest[i - 1][j] != 'X':
				ways += 1
		if j + 1 < m:
			if forest[i][j + 1] != 'X':
				ways += 1
		if j - 1 >= 0:
			if forest[i][j - 1] != 'X':
				ways += 1
		if p == start:
			if ways >= 2:
				wands += 1
		elif ways >= 3:
			wands += 1
		p = superpath[i][j]
	if wands == k:
		print('Impressed')
	else:
		print('Oops!')


def choices(a, i, j, nr, nc, v):
	vals = []
	for (k, l) in [[i, j - 1], [i - 1, j], [i + 1, j], [i, j + 1]]:
		if k < 0 or l < 0 or k >= nr or (l >= nc) or (a[k][l] == 'X') or (v[k][l] == 1):
			continue
		vals.append([k, l])
	return vals

def dfs(a, i, j, nr, nc, d, v):
	visited[i][j] = 1
	if a[i][j] == '*':
		return d
	vals = choices(a, i, j, nr, nc, v)
	if len(vals) == 0:
		return -1
	if len(vals) > 1:
		d += 1
	for (k, l) in vals:
		result = dfs(a, k, l, nr, nc, d, v)
		if result >= 0:
			return result
	return -1
t = int(input())
for nt in range(t):
	(hr, hc) = (0, 0)
	(nr, nc) = [int(i) for i in input().split(' ')]
	a = []
	for i in range(nr):
		s = input()
		x = s.find('M')
		if x > -1:
			(hr, hc) = (i, x)
		a.append([i for i in s])
	p = int(input())
	turns = 0
	visited = []
	for i in range(nr):
		visited.append([0 for j in range(nc)])
	turns = dfs(a, hr, hc, nr, nc, 0, visited)
	if turns == p:
		print('Impressed')
	else:
		print('Oops!')


class Point:

	def __init__(self, x, y, item):
		self.x = x
		self.y = y
		self.item = item

	def __eq__(self, other):
		if self.x == other.x and self.y == other.y:
			return True
		return False

	def __ne__(self, other):
		return not self.__eq__(other)

	def __repr__(self):
		return 'X: ' + str(self.x) + '; Y: ' + str(self.y) + '; Item: ' + str(self.item) + '||| '

def FoundGermiona(grid):
	for (idx, row) in enumerate(grid):
		for (idy, cell) in enumerate(row):
			if cell == 'M':
				return Point(idx, idy, 'M')

def GetNeighbors(grid, cp, rows, columns):
	point_list = []
	if cp.x > 0:
		itm = grid[cp.x - 1][cp.y]
		if itm == '.' or itm == '*':
			point_list.append(Point(cp.x - 1, cp.y, itm))
	if cp.y - 1 >= 0:
		itm = grid[cp.x][cp.y - 1]
		if itm == '.' or itm == '*':
			point_list.append(Point(cp.x, cp.y - 1, itm))
	if cp.y < columns - 1:
		itm = grid[cp.x][cp.y + 1]
		if itm == '.' or itm == '*':
			point_list.append(Point(cp.x, cp.y + 1, itm))
	if cp.x < rows - 1:
		itm = grid[cp.x + 1][cp.y]
		if itm == '.' or itm == '*':
			point_list.append(Point(cp.x + 1, cp.y, itm))
	return point_list

def deepcopy(A):
	rt = []
	for elem in A:
		if isinstance(elem, list):
			rt.append(deepcopy(elem))
		else:
			rt.append(elem)
	return rt

def found_way(path, grid, rows, columns):
	neighbors = GetNeighbors(grid, path[len(path) - 1], rows, columns)
	if neighbors is None:
		return None
	for n in neighbors:
		if n.item == '*':
			path.append(n)
			return path
	new_way = None
	for n in neighbors:
		if n not in path:
			new_pass = deepcopy(path)
			new_pass.append(n)
			way = found_way(new_pass, grid, rows, columns)
			if way is not None:
				new_way = way
	return new_way
cnt = int(input())
for i in range(cnt):
	(rows, columns) = [int(x) for x in input().split()]
	grid = []
	for row in range(rows):
		r = [x for x in input()]
		grid.append(r)
	count_wawe = int(input())
	p = FoundGermiona(grid)
	path = [p]
	path = found_way(path, grid, rows, columns)
	wawe_cnt = 0
	for ptn in path:
		nbrs = GetNeighbors(grid, ptn, rows, columns)
		if len(nbrs) > 2 and ptn.item != '*':
			wawe_cnt += 1
		if len(nbrs) == 2 and (p == ptn or ptn == path[1]):
			wawe_cnt += 1
	if wawe_cnt == count_wawe:
		print('Impressed')
	else:
		print('Oops!')


T = int(input())

def find(matrix, char):
	char_row = [row for row in range(len(matrix)) if char in matrix[row]][0]
	char_col = matrix[char_row].index(char)
	return (char_row, char_col)

def sum_coords(a, b):
	return (a[0] + b[0], a[1] + b[1])

def find_path(matrix):
	(N, M) = (len(matrix), len(matrix[0]))
	start = find(matrix, 'M')
	end = find(matrix, '*')
	paths = [[start]]

	def get(coord):
		return matrix[coord[0]][coord[1]]
	while paths:
		new_paths = []
		for path in paths:
			for delta in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				coord = sum_coords(path[-1], delta)
				if 0 <= coord[0] < N and 0 <= coord[1] < M and (len(path) == 1 or coord != path[-2]) and (get(coord) != 'X'):
					if coord == end:
						return path + [coord]
					else:
						new_paths.append(path + [coord])
		paths = new_paths
	return None

def count_waves(matrix, path):
	(N, M) = (len(matrix), len(matrix[0]))

	def get(coord):
		return matrix[coord[0]][coord[1]]
	count = 0
	for (i, path_coord) in enumerate(path[:-1]):
		neighbors = [sum_coords(path_coord, delta) for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]]
		options = [coord for coord in neighbors if 0 <= coord[0] < N and 0 <= coord[1] < M and (get(coord) != 'X')]
		if len(options) > (2 if i > 0 else 1):
			count += 1
	return count
for _i in range(T):
	(N, M) = map(int, input().split())
	matrix = []
	for row in range(N):
		matrix.append(input())
	K = int(input())
	path = find_path(matrix)
	count = count_waves(matrix, path)
	print('Impressed' if K == count else 'Oops!')


def pathfinder(row, col, k, map):
	if map[row][col] == '-':
		return -1
	if map[row][col] == 'X':
		return -1
	if map[row][col] == 'M':
		map[row][col] = '-'
	if map[row][col] == '*':
		return k
	if map[row][col] == '.':
		map[row][col] = '-'
	options = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
	options = [pair for pair in options if pair[0] >= 0 and pair[0] < len(map) and (pair[1] >= 0) and (pair[1] < len(map[0]))]
	options = [pair for pair in options if map[pair[0]][pair[1]] == '.' or map[pair[0]][pair[1]] == '*']
	mx = -1
	if len(options) == 0:
		return -1
	elif len(options) == 1:
		(r, c) = options[0]
		return pathfinder(r, c, k, map)
	else:
		k += 1
		for pair in options:
			(r, c) = pair
			temp = pathfinder(r, c, k, map)
			if temp > mx:
				mx = temp
		return mx
for t in range(int(input())):
	(rows, cols) = [int(x) for x in input().split()]
	map = [list(input()) for y in range(rows)]
	k = int(input())
	for i in range(rows):
		for j in range(cols):
			if map[i][j] == 'M':
				(r, c) = (i, j)
				break
	waves = pathfinder(r, c, 0, map)
	print('Impressed' if waves == k else 'Oops!')


from collections import deque

def _find_cell(forest, cell):
	for (i, _) in enumerate(forest):
		for (j, _) in enumerate(forest[i]):
			if forest[i][j] == cell:
				return (i, j)

def _get_adj(forest, i, j):
	(maxi, maxj) = (len(forest), len(forest[0]))
	adj = []
	for n in (-1, 1):
		newi = i + n
		if 0 <= newi < maxi and forest[newi][j] != 'X':
			adj.append((newi, j))
	for m in (-1, 1):
		newj = j + m
		if 0 <= newj < maxj and forest[i][newj] != 'X':
			adj.append((i, newj))
	return adj

def _explore(forest, si, sj, ei, ej):
	seen = set()
	(prev, q) = ({}, deque())
	q.append((si, sj))
	while q:
		(curri, currj) = q.pop()
		if curri == ei and currj == ej:
			break
		for cell in _get_adj(forest, curri, currj):
			if cell not in seen:
				seen.add(cell)
				q.appendleft(cell)
				prev[cell] = (curri, currj)
	(curri, currj) = (ei, ej)
	path = deque()
	while curri != si or currj != sj:
		(curri, currj) = prev[curri, currj]
		path.appendleft((curri, currj))
	return path

def _estimate_k(forest, path):
	currk = 0
	seen = set()
	for (i, j) in path:
		seen.add((i, j))
		adj_cells = [cell for cell in _get_adj(forest, i, j) if cell not in seen]
		if len(adj_cells) > 1:
			currk += 1
	return currk

def explore(forest, k):
	(si, sj) = _find_cell(forest, 'M')
	(ei, ej) = _find_cell(forest, '*')
	path = _explore(forest, si, sj, ei, ej)
	return _estimate_k(forest, path) == k
t = int(input())
for _ in range(t):
	(n, m) = [int(el) for el in input().split()]
	forest = [list(input()) for _ in range(n)]
	k = int(input())
	print('Impressed' if explore(forest, k) else 'Oops!')


def getWaysOut(r, c, maxr, maxc, grid, mystack):
	ways = []
	if r > 0 and grid[r - 1][c] == '.' and ((r - 1, c) not in mystack):
		ways.append((r - 1, c))
	if c > 0 and grid[r][c - 1] == '.' and ((r, c - 1) not in mystack):
		ways.append((r, c - 1))
	if c < maxc - 1 and grid[r][c + 1] == '.' and ((r, c + 1) not in mystack):
		ways.append((r, c + 1))
	if r < maxr - 1 and grid[r + 1][c] == '.' and ((r + 1, c) not in mystack):
		ways.append((r + 1, c))
	return ways

def dfs(r, c, pr, pc, foodr, foodc, grid):
	mystack = [(pr, pc, 0)]
	while (pr, pc) != (foodr, foodc):
		(pr, pc, n) = mystack.pop()
		if grid[pr][pc] == '.':
			grid[pr][pc] = 'O'
			waysOut = getWaysOut(pr, pc, r, c, grid, mystack)
			if len(waysOut) > 1:
				for (wr, wc) in waysOut:
					mystack.append((wr, wc, n + 1))
			elif len(waysOut) == 1:
				mystack.append((waysOut[0][0], waysOut[0][1], n))
			if (pr, pc) == (foodr, foodc):
				return n
	print('We should never get here if there is a valid solution!')
	return 0
n = int(input())
for _ in range(n):
	(rows, cols) = [int(x) for x in input().split()]
	grid = []
	for i in range(rows):
		grid.append([x for x in input()])
		if 'M' in grid[-1]:
			start_r = i
			start_c = grid[-1].index('M')
			grid[start_r][start_c] = '.'
		if '*' in grid[-1]:
			end_r = i
			end_c = grid[-1].index('*')
			grid[end_r][end_c] = '.'
	guess = int(input())
	numOfTurns = dfs(rows, cols, start_r, start_c, end_r, end_c, grid)
	if guess == numOfTurns:
		print('Impressed')
	else:
		print('Oops!')


def dfs(F, V, i, j, N, M):
	if V[i][j]:
		return -1
	V[i][j] = True
	if F[i][j] == '*':
		return 0
	spawn = 0
	ret = -1
	if i - 1 >= 0 and F[i - 1][j] != 'X':
		spawn += 1
		ret = max(ret, dfs(F, V, i - 1, j, N, M))
	if j - 1 >= 0 and F[i][j - 1] != 'X':
		spawn += 1
		ret = max(ret, dfs(F, V, i, j - 1, N, M))
	if i + 1 < N and F[i + 1][j] != 'X':
		spawn += 1
		ret = max(ret, dfs(F, V, i + 1, j, N, M))
	if j + 1 < M and F[i][j + 1] != 'X':
		spawn += 1
		ret = max(ret, dfs(F, V, i, j + 1, N, M))
	if ret != -1:
		if F[i][j] == 'M' and spawn > 1:
			ret += 1
		elif spawn > 2:
			ret += 1
	return ret
T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	F = [list(input()) for x in range(N)]
	K = int(input())
	for i in range(N):
		if 'M' in F[i]:
			(x, y) = (i, F[i].index('M'))
			break
	V = [[False] * M for x in range(N)]
	if dfs(F, V, x, y, N, M) == K:
		print('Impressed')
	else:
		print('Oops!')


__author__ = 'Shivani'

def dfs(l, d, i, j, k, f):
	cnt = 0
	if i == len(l) or j == len(l[i]) or i < 0 or (j < 0) or (l[i][j] == '0') or (l[i][j] == 'X') or (d > k) or (f[0] == True):
		return
	if l[i][j] == '*' and d == k:
		print('Impressed')
		f[0] = True
		return
	l[i][j] = '0'
	if i < len(l) - 1 and (l[i + 1][j] == '.' or l[i + 1][j] == '*'):
		cnt += 1
	if i > 0 and l[i - 1][j] == '.' or l[i - 1][j] == '*':
		cnt += 1
	if j < len(l[i]) - 1 and (l[i][j + 1] == '.' or l[i][j + 1] == '*'):
		cnt += 1
	if j > 0 and (l[i][j - 1] == '.' or l[i][j - 1] == '*'):
		cnt += 1
	if cnt > 1:
		d += 1
	dfs(l, d, i + 1, j, k, f)
	dfs(l, d, i - 1, j, k, f)
	dfs(l, d, i, j + 1, k, f)
	dfs(l, d, i, j - 1, k, f)

def luck(l, k, i, j):
	f = [False]
	dfs(l, 0, i, j, k, f)
	if f[0] == False:
		print('Oops!')

def find(l):
	for i in range(len(l)):
		if l[i] == 'M':
			return i
	return -1

def main():
	for i in range(int(input())):
		(m, n) = input().split()
		(m, n) = (int(m), int(n))
		l = []
		(r, c) = (-1, -1)
		for j in range(m):
			t = list(input())
			if c == -1:
				c = find(t)
				if c != -1:
					r = j
			l.append(t)
		k = int(input())
		luck(l, k, r, c)
main()


from collections import defaultdict, deque
edges = [(0, 1), (1, 0), (-1, 0), (0, -1)]
TREE = 'X'

def bfs(mat, start, dest):

	def valid_index(len_row, len_col):

		def predicate(pos):
			return 0 <= pos[0] < len_row and 0 <= pos[1] < len_col and (mat[pos[0]][pos[1]] != TREE)
		return predicate
	visited = set()
	queue = deque()
	queue.append(start)
	counter = defaultdict(int)
	predicate = valid_index(len(mat), len(mat[0]))
	while queue:
		curr = queue.popleft()
		visited.add(curr)
		if curr == dest:
			return counter[curr]
		nxts = set((tuple(map(sum, zip(edge, curr))) for edge in edges))
		nxts = set(filter(predicate, nxts)) - visited
		new_count = 1 if len(nxts) > 1 else 0
		for nxt in nxts:
			if nxt not in visited and nxt not in queue:
				queue.append(nxt)
				counter[nxt] = counter[curr] + new_count
	return -1
DEST = '*'
START = 'M'
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	mat = []
	for i in range(N):
		row = list(input())
		if START in row:
			start = (i, row.index(START))
		if DEST in row:
			dest = (i, row.index(DEST))
		mat.append(row)
	K = int(input())
	if K == bfs(mat, start, dest):
		print('Impressed')
	else:
		print('Oops!')


import sys
sys.setrecursionlimit(10000)

def readMatrix(y, x):
	matrix = []
	for _ in range(y):
		matrix.append([c for c in input()])
	assert len(matrix) == y
	assert len(matrix[0]) == x
	return matrix

def findM(mat):
	for y in range(len(mat)):
		if 'M' in mat[y]:
			return (y, mat[y].index('M'))
	assert False, 'M not found'

def numTurns(mat):
	start = findM(mat)
	return numTurnsFrom(start, mat, [])

def numTurnsFrom(loc, mat, cameFrom, count=0):
	(y, x) = loc
	if mat[y][x] == '*':
		return count
	neighborDeltas = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	neighbors = []
	for (dy, dx) in neighborDeltas:
		yP = y + dy
		xP = x + dx
		if -1 < yP < len(mat) and -1 < xP < len(mat[0]) and ((yP, xP) not in cameFrom) and (mat[yP][xP] != 'X'):
			neighbors.append((yP, xP))
	cameFrom.append(loc)
	if len(neighbors) > 1:
		count += 1
	if len(neighbors) == 0:
		return float('Inf')
	return min([numTurnsFrom(neighbor, mat, cameFrom=cameFrom, count=count) for neighbor in neighbors])
assert numTurns([['*', '.', 'M'], ['.', 'X', '.']]) == 1
for _ in range(int(input())):
	(y, x) = map(int, input().split())
	matrix = readMatrix(y, x)
	goal = int(input())
	num = numTurns(matrix)
	if num == goal:
		print('Impressed')
	else:
		print('Oops!')


def choices(a, i, j, rows, cols, v):
	vals = []
	for (k, l) in [[i, j - 1], [i - 1, j], [i + 1, j], [i, j + 1]]:
		if k < 0 or l < 0 or k >= rows or (l >= cols) or (a[k][l] == 'X') or (v[k][l] == 1):
			continue
		vals.append([k, l])
	return vals

def dfs(a, i, j, rows, cols, v, turns):
	v[i][j] = 1
	if a[i][j] == '*':
		return turns
	vals = choices(a, i, j, rows, cols, v)
	if len(vals) > 1:
		turns += 1
	for (k, l) in vals:
		if v[k][l] != 1:
			d = dfs(a, k, l, rows, cols, v, turns)
			if d > 0:
				return d
	return 0
for t in range(int(input())):
	(hrow, hcol) = (0, 0)
	(rows, cols) = [int(i) for i in input().split(' ')]
	grid = []
	for i in range(rows):
		s = input()
		x = s.find('M')
		if x > -1:
			(hrow, hcol) = (i, x)
		grid.append([i for i in s])
	p = int(input())
	visited = [[0 for j in range(cols)] for i in range(rows)]
	turns = dfs(grid, hrow, hcol, rows, cols, visited, 0)
	if turns == p:
		print('Impressed')
	else:
		print('Oops!')


class Node(object):

	def __init__(self, pos_y, pos_x):
		self.pos_y = pos_y
		self.pos_x = pos_x
		self.dirr = 0

	def next(self):
		while self.dirr <= 3:
			if self.dirr == 0:
				yield Node(self.pos_y, self.pos_x - 1)
			elif self.dirr == 1:
				yield Node(self.pos_y, self.pos_x + 1)
			elif self.dirr == 2:
				yield Node(self.pos_y - 1, self.pos_x)
			else:
				yield Node(self.pos_y + 1, self.pos_x)
			self.dirr += 1

	def __eq__(self, oth):
		return self.pos_y == oth.pos_y and self.pos_x == oth.pos_x

	def __str__(self):
		return '{}:{}'.format(self.pos_y, self.pos_x)

	def __repr__(self):
		return '{}:{}'.format(self.pos_y, self.pos_x)

	def __and__(self, oth):
		return Node(abs(self.pos_y - oth.pos_y), abs(self.pos_x - oth.pos_x))

class Solution(object):

	def __init__(self, rows, cols, forest, k_sugested):
		self.visited = [x[:] for x in [[False] * cols] * rows]
		self.forest = forest
		self.k_count = 0
		self.cols = cols
		self.rows = rows
		self.kacc = k_sugested
		self.stack = []

	def search_start_end(self, rows, cols):
		(start, end) = (None, None)
		for posy in range(rows):
			for posx in range(cols):
				if self.forest[posy][posx] == 'M':
					start = Node(posy, posx)
					if end is not None and start is not None:
						return (start, end)
				elif self.forest[posy][posx] == '*':
					end = Node(posy, posx)
					if end is not None and start is not None:
						return (start, end)

	def visit(self, node):
		self.visited[node.pos_y][node.pos_x] = True

	def mov_valid(self, node):
		return 0 <= node.pos_x < self.cols and 0 <= node.pos_y < self.rows and (self.forest[node.pos_y][node.pos_x] in ('.', '*')) and (not self.visited[node.pos_y][node.pos_x])

	def solve(self):
		(start, end) = self.search_start_end(self.rows, self.cols)

		def search(pos):
			self.visit(pos)
			if pos == end:
				self.stack.append(pos)
				return True
			arr = []
			for opt in pos.next():
				if self.mov_valid(opt):
					arr.append(opt)
			for opt in arr:
				if search(opt):
					if len(arr) > 1:
						self.k_count += 1
					self.stack.append(opt)
					return True
			return False
		search(start)
		if self.k_count == self.kacc:
			return 'Impressed'
		else:
			return 'Oops!'
for _ in range(int(input())):
	(nval, mval) = list(map(int, input().split()))
	mat = []
	for _ in range(nval):
		mat.append(input())
	kval = int(input())
	print(Solution(nval, mval, mat, kval).solve())


def check_bounds(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def dfs(grid, visited, i, j, N, M, wands):
	if not check_bounds(i, j, N, M) or (i, j) in visited:
		return
	if grid[i][j] == '*':
		return wands
	visited[i, j] = True
	possibilities = []
	deltas = [(0, 1), (1, 0), (0, -1), (-1, 0)]
	for (dx, dy) in deltas:
		if check_bounds(i + dx, j + dy, N, M) and grid[i + dx][j + dy] in ('.', '*') and ((i + dx, j + dy) not in visited):
			possibilities.append((i + dx, j + dy))
	if len(possibilities) > 1:
		wands += 1
	for (new_x, new_y) in possibilities:
		result = dfs(grid, visited, new_x, new_y, N, M, wands)
		visited[new_x, new_y] = True
		if result is not None:
			return result
	return
for testcase in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	grid = []
	(start_x, start_y) = (0, 0)
	for i in range(N):
		grid.append(input())
		if 'M' in grid[-1]:
			(start_x, start_y) = (i, grid[-1].index('M'))
	K = int(input())
	if dfs(grid, {}, start_x, start_y, N, M, 0) == K:
		print('Impressed')
	else:
		print('Oops!')


from collections import defaultdict

def hermionesWand(arr, K, max_x, max_y):
	for (idx, line) in enumerate(arr):
		for inner_idx in range(len(line)):
			if line[inner_idx] == 'M':
				h = (idx, inner_idx)
			if line[inner_idx] == '*':
				e = (idx, inner_idx)
	st = [h]
	tracker = defaultdict(int)
	tracker[h] = 0
	while st:
		curr = st.pop()
		if curr == e:
			return tracker[curr] == K
		inner_st = set()
		if curr[0] > 0 and (arr[curr[0] - 1][curr[1]] == '.' or arr[curr[0] - 1][curr[1]] == '*') and ((curr[0] - 1, curr[1]) not in tracker):
			inner_st.add((curr[0] - 1, curr[1]))
		if curr[1] > 0 and (arr[curr[0]][curr[1] - 1] == '.' or arr[curr[0]][curr[1] - 1] == '*') and ((curr[0], curr[1] - 1) not in tracker):
			inner_st.add((curr[0], curr[1] - 1))
		if curr[0] < max_y - 1 and (arr[curr[0] + 1][curr[1]] == '.' or arr[curr[0] + 1][curr[1]] == '*') and ((curr[0] + 1, curr[1]) not in tracker):
			inner_st.add((curr[0] + 1, curr[1]))
		if curr[1] < max_x - 1 and (arr[curr[0]][curr[1] + 1] == '.' or arr[curr[0]][curr[1] + 1] == '*') and ((curr[0], curr[1] + 1) not in tracker):
			inner_st.add((curr[0], curr[1] + 1))
		if len(inner_st) > 1:
			tracker[curr] += 1
		for n in inner_st:
			tracker[n] = tracker[curr]
			st.append(n)
	return False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for line in range(n):
		a.append(list(input()))
	k = int(input())
	if hermionesWand(a, k, m, n):
		print('Impressed')
	else:
		print('Oops!')


from collections import defaultdict

def hermionesWand(arr, K, max_x, max_y):
	for (idx, line) in enumerate(arr):
		for inner_idx in range(len(line)):
			if line[inner_idx] == 'M':
				h = (idx, inner_idx)
			if line[inner_idx] == '*':
				e = (idx, inner_idx)
	st = [h]
	tracker = defaultdict(int)
	tracker[h] = 0
	while st:
		curr = st.pop()
		if curr == e:
			return tracker[curr] == K
		inner_st = set()
		if (curr[0] > 0 and (arr[curr[0] - 1][curr[1]] == '.' or arr[curr[0] - 1][curr[1]] == '*')) and (curr[0] - 1, curr[1]) not in tracker:
			inner_st.add((curr[0] - 1, curr[1]))
		if (curr[1] > 0 and (arr[curr[0]][curr[1] - 1] == '.' or arr[curr[0]][curr[1] - 1] == '*')) and (curr[0], curr[1] - 1) not in tracker:
			inner_st.add((curr[0], curr[1] - 1))
		if (curr[0] < max_y - 1 and (arr[curr[0] + 1][curr[1]] == '.' or arr[curr[0] + 1][curr[1]] == '*')) and (curr[0] + 1, curr[1]) not in tracker:
			inner_st.add((curr[0] + 1, curr[1]))
		if (curr[1] < max_x - 1 and (arr[curr[0]][curr[1] + 1] == '.' or arr[curr[0]][curr[1] + 1] == '*')) and (curr[0], curr[1] + 1) not in tracker:
			inner_st.add((curr[0], curr[1] + 1))
		if len(inner_st) > 1:
			tracker[curr] += 1
		for n in inner_st:
			tracker[n] = tracker[curr]
			st.append(n)
	return False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for line in range(n):
		a.append(list(input()))
	k = int(input())
	if hermionesWand(a, k, m, n):
		print('Impressed')
	else:
		print('Oops!')


def find_children(pos, board, visited):
	(x, y) = pos

	def valid_pos(x, y):
		return 0 <= x < len(board) and 0 <= y < len(board[x]) and (board[x][y] != 'X') and ((x, y) not in visited)
	children = []
	for (i, j) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
		if valid_pos(i, j):
			children.append((i, j))
	return children

def start_pos(board):
	for i in range(len(board)):
		for j in range(len(board[i])):
			if board[i][j] == 'M':
				return (i, j)

def goal_pos(board):
	for i in range(len(board)):
		for j in range(len(board[i])):
			if board[i][j] == '*':
				return (i, j)

def walk(start, goal, board):
	stack = [start]
	visited = []
	path = {}
	while stack:
		curr = stack.pop(0)
		visited.append(curr)
		if curr == goal:
			break
		children = find_children(curr, board, visited)
		for child in children:
			path[child] = (curr, 1 if len(children) > 1 else 0)
		stack = children + stack
	luck = 0
	while curr is not None:
		(curr, val) = path.get(curr, (None, 0))
		luck += val
	return luck

def create_board(rows):
	board = []
	for row in rows:
		board.append(list(row))
	return board
test_cases = int(input())
for _ in range(test_cases):
	(rows, cols) = input().split()
	board = [list(input()) for _ in range(int(rows))]
	waves = int(input())
	start = start_pos(board)
	goal = goal_pos(board)
	if waves == walk(start, goal, board):
		print('Impressed')
	else:
		print('Oops!')


def get_pos(a, c):
	for (i, l) in enumerate(a):
		for (j, d) in enumerate(l):
			if d == c:
				return (i, j)

def is_fork(i, j, hi, hj, n, m, a):
	roads = 0
	for (dn, dm) in ((0, -1), (0, 1), (-1, 0), (1, 0)):
		(ni, mi) = (i + dn, j + dm)
		if ni >= n or ni < 0:
			continue
		if mi >= m or mi < 0:
			continue
		if a[ni][mi] != 'X':
			roads += 1
	if i == hi and j == hj:
		roads += 1
	return roads > 2

def dfs(i, j, hi, hj, n, m, a, seen):
	seen[i][j] = 2
	if a[i][j] == '*':
		return (True, 0)
	for (dn, dm) in ((0, -1), (0, 1), (-1, 0), (1, 0)):
		(ni, mi) = (i + dn, j + dm)
		if ni >= n or ni < 0:
			continue
		if mi >= m or mi < 0:
			continue
		if a[ni][mi] == 'X':
			continue
		if seen[ni][mi] == 0:
			(r, f) = dfs(ni, mi, hi, hj, n, m, a, seen)
			if r:
				if is_fork(i, j, hi, hj, n, m, a):
					f += 1
				return (True, f)
	return (False, 0)

def check_count(n, m, a, expected):
	seen = [[0 for _ in range(m)] for _ in range(n)]
	(hi, hj) = get_pos(a, 'M')
	(r, f) = dfs(hi, hj, hi, hj, n, m, a, seen)
	return f == expected

def main():
	t = int(input())
	for ti in range(0, t):
		n_m = input().split()
		n = int(n_m[0])
		m = int(n_m[1])
		a = [[0 for _ in range(m)] for _ in range(n)]
		for ni in range(n):
			l = input()
			for (mi, c) in enumerate(l):
				a[ni][mi] = c
		k = int(input())
		if check_count(n, m, a, k):
			print('Impressed')
		else:
			print('Oops!')
main()


import fileinput
inputs = []
for line in fileinput.input():
	inputs.append([x for x in line.strip().split()])
(T, C, tpos) = (int(inputs[0][0]), inputs[1:], 0)

def dfs_paths(graph, start, goal):
	stack = [(start, [start])]
	while stack:
		(vertex, path) = stack.pop()
		for next in graph[vertex] - set(path):
			if next == goal:
				yield (path + [next])
			else:
				stack.append((next, path + [next]))
for t in range(T):
	(N, M) = (int(C[tpos][0]), int(C[tpos][1]))
	(matrix, K) = (C[tpos + 1:tpos + 1 + N], int(C[tpos + 1 + N][0]))
	(start, end, graph) = (None, None, {})
	for row in range(N):
		matrix[row] = list(matrix[row][0])
	for row in range(N):
		for col in range(M):
			strrow = '0' + str(row) if row < 10 else str(row)
			strcol = '0' + str(col) if col < 10 else str(col)
			graph[strrow + strcol] = set([])
	for row in range(N):
		for col in range(M):
			strrow = '0' + str(row) if row < 10 else str(row)
			strcol = '0' + str(col) if col < 10 else str(col)
			if matrix[row][col] == 'M':
				start = strrow + strcol
			if matrix[row][col] == '*':
				end = strrow + strcol
			if not matrix[row][col] == 'X':
				if row > 0:
					if not matrix[row - 1][col] == 'X':
						strrowless1 = '0' + str(row - 1) if row - 1 < 10 else str(row - 1)
						graph[strrow + strcol].add(strrowless1 + strcol)
				if col < M - 1:
					if not matrix[row][col + 1] == 'X':
						strcolplus1 = '0' + str(col + 1) if col + 1 < 10 else str(col + 1)
						graph[strrow + strcol].add(strrow + strcolplus1)
				if row < N - 1:
					if not matrix[row + 1][col] == 'X':
						strrowplus1 = '0' + str(row + 1) if row + 1 < 10 else str(row + 1)
						graph[strrow + strcol].add(strrowplus1 + strcol)
				if col > 0:
					if not matrix[row][col - 1] == 'X':
						strcolless1 = '0' + str(col - 1) if col - 1 < 10 else str(col - 1)
						graph[strrow + strcol].add(strrow + strcolless1)
	(graphsm, deadends, waves) = ({}, {}, 0)
	for key in graph:
		if key == start or key == end or len(graph[key]) > 1:
			graphsm[key] = graph[key].copy()
		elif len(graph[key]) == 1:
			deadends[key] = graph[key].copy()
	for key in deadends:
		connected = deadends[key]
		for cell in connected:
			graphsm[cell].remove(key)
	path = list(dfs_paths(graphsm, start, end))[0]
	for y in path:
		options = len(graph[y])
		if y == start and options > 1:
			waves += 1
		elif not y == end and options > 2:
			waves += 1
	res = 'Impressed' if K == waves else 'Oops!'
	tpos += 2 + N
	print(res)


from collections import defaultdict

def hermionesWand(arr, K, max_x, max_y):
	for (idx, line) in enumerate(arr):
		for inner_idx in range(len(line)):
			if line[inner_idx] == 'M':
				h = (idx, inner_idx)
			if line[inner_idx] == '*':
				e = (idx, inner_idx)
	st = [h]
	tracker = defaultdict(int)
	tracker[h] = 0
	while st:
		curr = st.pop()
		if curr == e:
			return tracker[curr] == K
		inner_st = set()
		if (curr[0] > 0 and (arr[curr[0] - 1][curr[1]] == '.' or arr[curr[0] - 1][curr[1]] == '*')) and (curr[0] - 1, curr[1]) not in tracker:
			inner_st.add((curr[0] - 1, curr[1]))
		if (curr[1] > 0 and (arr[curr[0]][curr[1] - 1] == '.' or arr[curr[0]][curr[1] - 1] == '*')) and (curr[0], curr[1] - 1) not in tracker:
			inner_st.add((curr[0], curr[1] - 1))
		if (curr[0] < max_y - 1 and (arr[curr[0] + 1][curr[1]] == '.' or arr[curr[0] + 1][curr[1]] == '*')) and (curr[0] + 1, curr[1]) not in tracker:
			inner_st.add((curr[0] + 1, curr[1]))
		if (curr[1] < max_x - 1 and (arr[curr[0]][curr[1] + 1] == '.' or arr[curr[0]][curr[1] + 1] == '*')) and (curr[0], curr[1] + 1) not in tracker:
			inner_st.add((curr[0], curr[1] + 1))
		if len(inner_st) > 1:
			tracker[curr] += 1
		for n in inner_st:
			tracker[n] = tracker[curr]
			st.append(n)
	return False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for line in range(n):
		a.append(list(input()))
	k = int(input())
	if hermionesWand(a, k, m, n):
		print('Impressed')
	else:
		print('Oops!')


from collections import deque
T = int(input())
for i in range(0, T):
	l = []
	(N, M) = map(int, input().split(' '))
	for j in range(0, N):
		l.append(input().rstrip())
	K = int(input())
	visited = set()
	queue = deque()
	s = None
	d = None
	for i in range(0, N):
		try:
			j = l[i].index('M')
			s = (i, j)
		except ValueError:
			pass
	for i in range(0, N):
		try:
			j = l[i].index('*')
			d = (i, j)
		except ValueError:
			pass
	dist = {}
	queue.append(s)
	visited.add(s)
	dist[s] = 0
	while len(queue) != 0:
		u = queue.popleft()
		(i, j) = u
		if l[i][j] == '*':
			break
		adj = []
		if i - 1 >= 0 and l[i - 1][j] != 'X' and ((i - 1, j) not in visited):
			adj.append((i - 1, j))
		if i + 1 < N and l[i + 1][j] != 'X' and ((i + 1, j) not in visited):
			adj.append((i + 1, j))
		if j - 1 >= 0 and l[i][j - 1] != 'X' and ((i, j - 1) not in visited):
			adj.append((i, j - 1))
		if j + 1 < M and l[i][j + 1] != 'X' and ((i, j + 1) not in visited):
			adj.append((i, j + 1))
		for v in adj:
			if len(adj) > 1:
				dist[v] = dist[u] + 1
			else:
				dist[v] = dist[u]
			visited.add(v)
			queue.append(v)
	if dist[d] == K:
		print('Impressed')
	else:
		print('Oops!')


import collections
for t in range(int(input())):
	(h, w) = list(map(int, input().split()))
	terrain = list(map(lambda n: input(), range(h)))
	guess = int(input())
	graph = {}
	for y in range(h):
		for x in range(w):
			if terrain[y][x] == 'M':
				start = (y, x)
			if terrain[y][x] == '*':
				end = (y, x)
	tree = {}
	queue = collections.deque([(None, start)])
	while len(queue):
		(root, n) = queue.popleft()
		(y, x) = n
		paths = []
		if y != 0 and terrain[y - 1][x] != 'X':
			paths.append((y - 1, x))
		if x != 0 and terrain[y][x - 1] != 'X':
			paths.append((y, x - 1))
		if y < h - 1 and terrain[y + 1][x] != 'X':
			paths.append((y + 1, x))
		if x < w - 1 and terrain[y][x + 1] != 'X':
			paths.append((y, x + 1))
		if root:
			paths.remove(root)
		tree[n] = {'root': root, 'paths': paths}
		for p in paths:
			queue.append((n, p))
	n = tree[end]
	waves = 0
	while n['root']:
		n = tree[n['root']]
		if len(n['paths']) > 1:
			waves += 1
	print('Impressed' if waves == guess else 'Oops!')


def successors(grid, size_x, size_y, x, y):
	suc = []
	for i in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
		(x, y) = i
		if x >= 0 and y >= 0 and (x < size_x) and (y < size_y) and (grid[x][y] in ('.', '*')):
			suc.append(i)
	return suc

def search(grid, size_x, size_y, x, y):
	discovered = [[False] * size_y for i in range(size_x)]
	stack = ((x, y, 0), None)
	while stack != None:
		(x, y, cost) = stack[0]
		stack = stack[1]
		if grid[x][y] == '*':
			return cost
		if not discovered[x][y]:
			discovered[x][y] = True
			suc = [(x, y) for (x, y) in successors(grid, size_x, size_y, x, y) if not discovered[x][y]]
			for (x, y) in suc:
				stack = ((x, y, cost + (1 if len(suc) > 1 else 0)), stack)

def get_m_pos(grid, size_x, size_y):
	for i in range(size_x):
		for j in range(size_y):
			if grid[i][j] == 'M':
				return (i, j)
for i in range(int(input())):
	(size_x, size_y) = [int(i) for i in input().split()]
	grid = []
	for j in range(size_x):
		grid.append(list(input()))
	l = int(input())
	(x, y) = get_m_pos(grid, size_x, size_y)
	if search(grid, size_x, size_y, x, y) == l:
		print('Impressed')
	else:
		print('Oops!')


from sys import stdin

def traverse_path(hermione_location, forest, direction, w):
	path_found = False
	wand_waves = 0
	next_move_options = ''
	next_move_is_exit = False
	if direction != 'r' and hermione_location[0] - 1 > -1:
		if forest[hermione_location[1]][hermione_location[0] - 1] == '.':
			next_move_options += 'l'
		elif forest[hermione_location[1]][hermione_location[0] - 1] == '*':
			next_move_options += 'l'
			next_move_is_exit = True
	if direction != 'l' and hermione_location[0] + 1 < len(forest[0]):
		if forest[hermione_location[1]][hermione_location[0] + 1] == '.':
			next_move_options += 'r'
		elif forest[hermione_location[1]][hermione_location[0] + 1] == '*':
			next_move_options += 'r'
			next_move_is_exit = True
	if direction != 'd' and hermione_location[1] - 1 > -1:
		if forest[hermione_location[1] - 1][hermione_location[0]] == '.':
			next_move_options += 'u'
		elif forest[hermione_location[1] - 1][hermione_location[0]] == '*':
			next_move_options += 'u'
			next_move_is_exit = True
	if direction != 'u' and hermione_location[1] + 1 < len(forest):
		if forest[hermione_location[1] + 1][hermione_location[0]] == '.':
			next_move_options += 'd'
		elif forest[hermione_location[1] + 1][hermione_location[0]] == '*':
			next_move_options += 'd'
			next_move_is_exit = True
	if next_move_is_exit == True:
		if len(next_move_options) == 1:
			return (True, 0)
		else:
			return (True, 1)
	if len(next_move_options) == 0:
		return (False, 0)
	elif len(next_move_options) == 1:
		if next_move_options == 'l':
			return traverse_path((hermione_location[0] - 1, hermione_location[1]), forest, next_move_options, w + ' ')
		elif next_move_options == 'r':
			return traverse_path((hermione_location[0] + 1, hermione_location[1]), forest, next_move_options, w + ' ')
		elif next_move_options == 'u':
			return traverse_path((hermione_location[0], hermione_location[1] - 1), forest, next_move_options, w + ' ')
		elif next_move_options == 'd':
			return traverse_path((hermione_location[0], hermione_location[1] + 1), forest, next_move_options, w + ' ')
	else:
		if 'l' in next_move_options:
			(path_found, wand_waves) = traverse_path((hermione_location[0] - 1, hermione_location[1]), forest, 'l', w + ' ')
			if path_found == True:
				return (True, wand_waves + 1)
		if 'r' in next_move_options:
			(path_found, wand_waves) = traverse_path((hermione_location[0] + 1, hermione_location[1]), forest, 'r', w + ' ')
			if path_found == True:
				return (True, wand_waves + 1)
		if 'u' in next_move_options:
			(path_found, wand_waves) = traverse_path((hermione_location[0], hermione_location[1] - 1), forest, 'u', w + ' ')
			if path_found == True:
				return (True, wand_waves + 1)
		if 'd' in next_move_options:
			(path_found, wand_waves) = traverse_path((hermione_location[0], hermione_location[1] + 1), forest, 'd', w + ' ')
			if path_found == True:
				return (True, wand_waves + 1)
		return (False, 0)

def main():
	t = int(stdin.readline())
	for x in range(t):
		forest = []
		hermione_location = (0, 0)
		wand_waves = 0
		reached_exit = False
		(n, m) = (int(i) for i in stdin.readline().rstrip('\n').split(' '))
		for y in range(n):
			forest.append(list(stdin.readline().rstrip('\n')))
		k = int(stdin.readline())
		for y in range(n):
			if 'M' in forest[y]:
				hermione_location = (forest[y].index('M'), y)
		(reached_exit, wand_waves) = traverse_path(hermione_location, forest, '', '')
		if reached_exit == True and wand_waves == k:
			print('Impressed')
		else:
			print('Oops!')
main()


T = int(input())
for t in range(T):
	(N, M) = (int(x) for x in input().split())
	forest = []
	for n in range(N):
		forest.append(input())
		m = forest[-1].find('M')
		if m != -1:
			start = (n, m)
	K = int(input())
	explored = set()

	def test(i, j):
		return 0 <= i < N and 0 <= j < M and (forest[i][j] == '.' or forest[i][j] == '*') and ((i, j) not in explored)

	def explore(i, j, k):
		if forest[i][j] == '*':
			if k == 0:
				print('Impressed')
			else:
				print('Oops!')
			return True
		explored.add((i, j))
		explore_list = [x for x in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)) if test(*x)]
		next_k = k if len(explore_list) == 1 else k - 1
		for (next_i, next_j) in explore_list:
			if explore(next_i, next_j, next_k):
				return True
		return False
	explore(start[0], start[1], K)


def DFS_aux(matrix, N, M, r, c, K):
	matrix[r][c] = '.'
	if DFS(matrix, N, M, r, c, K):
		return True

def DFS(matrix, N, M, r, c, K):
	if K >= 0 and (not (r < 0 or r >= N or c < 0 or (c >= M))):
		if matrix[r][c] == '*' and K == 0:
			return True
		elif matrix[r][c] == '.':
			matrix[r][c] = 'M'
			if waveWand(matrix, N, M, r, c):
				K -= 1
			if DFS(matrix, N, M, r - 1, c, K) or DFS(matrix, N, M, r + 1, c, K) or DFS(matrix, N, M, r, c - 1, K) or DFS(matrix, N, M, r, c + 1, K):
				return True

def waveWand(matrix, N, M, r, c):
	pathCount = 0
	if r - 1 >= 0 and (matrix[r - 1][c] == '.' or matrix[r - 1][c] == '*'):
		pathCount += 1
	if r + 1 < N and (matrix[r + 1][c] == '.' or matrix[r + 1][c] == '*'):
		pathCount += 1
	if c - 1 >= 0 and (matrix[r][c - 1] == '.' or matrix[r][c - 1] == '*'):
		pathCount += 1
	if c + 1 < M and (matrix[r][c + 1] == '.' or matrix[r][c + 1] == '*'):
		pathCount += 1
	if pathCount >= 2:
		return True
T = int(input())
for i in range(T):
	(N, M) = str(input()).split()
	forestMatrix = []
	hermione_r = None
	hermione_c = None
	for n in range(int(N)):
		forestMatrix.append(list(input()))
		if hermione_r == None and hermione_c == None:
			for m in range(int(M)):
				if forestMatrix[n][m] == 'M':
					hermione_r = n
					hermione_c = m
	K = int(input())
	if DFS_aux(forestMatrix, int(N), int(M), hermione_r, hermione_c, K):
		print('Impressed')
	else:
		print('Oops!')


def dfs(grid, i, j, visited):
	if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[i])) or ((i, j) in visited):
		return 10001
	elif grid[i][j] == '*':
		return 0
	else:
		visited.add((i, j))
		left = right = up = down = 0
		if not (i - 1, j) in visited and i > 0 and (grid[i - 1][j] in '.*'):
			left = 1
		if not (i + 1, j) in visited and i < len(grid) - 1 and (grid[i + 1][j] in '.*'):
			right = 1
		if not (i, j - 1) in visited and j > 0 and (grid[i][j - 1] in '.*'):
			up = 1
		if not (i, j + 1) in visited and j < len(grid[i]) - 1 and (grid[i][j + 1] in '.*'):
			down = 1
		ret = 0
		if left + right + up + down > 1:
			ret += 1
		if left:
			subret = dfs(grid, i - 1, j, visited)
			if subret < 10001:
				return ret + subret
		if right:
			subret = dfs(grid, i + 1, j, visited)
			if subret < 10001:
				return ret + subret
		if up:
			subret = dfs(grid, i, j - 1, visited)
			if subret < 10001:
				return ret + subret
		if down:
			subret = dfs(grid, i, j + 1, visited)
			if subret < 10001:
				return ret + subret
		visited.remove((i, j))
		return 10001

def findStartingPos(grid):
	for i in range(len(grid)):
		for j in range(len(grid[i])):
			if grid[i][j] == 'M':
				return (i, j)
	print(grid)
	return None
T = int(input())
for _ in range(T):
	MN = [int(x) for x in input().split()]
	(M, N) = (MN[0], MN[1])
	grid = [input() for _ in range(M)]
	K = int(input())
	(i, j) = findStartingPos(grid)
	expK = dfs(grid, i, j, set())
	if K == expK:
		print('Impressed')
	else:
		print('Oops!')


from collections import defaultdict

def hermionesWand(arr, K, max_x, max_y):
	for (idx, line) in enumerate(arr):
		for inner_idx in range(len(line)):
			if line[inner_idx] == 'M':
				h = (idx, inner_idx)
			if line[inner_idx] == '*':
				e = (idx, inner_idx)
	st = [h]
	tracker = defaultdict(int)
	tracker[h] = 0
	while st:
		curr = st.pop()
		if curr == e:
			return tracker[curr] == K
		inner_st = set()
		if (curr[0] > 0 and (arr[curr[0] - 1][curr[1]] == '.' or arr[curr[0] - 1][curr[1]] == '*')) and (curr[0] - 1, curr[1]) not in tracker:
			inner_st.add((curr[0] - 1, curr[1]))
		if (curr[1] > 0 and (arr[curr[0]][curr[1] - 1] == '.' or arr[curr[0]][curr[1] - 1] == '*')) and (curr[0], curr[1] - 1) not in tracker:
			inner_st.add((curr[0], curr[1] - 1))
		if (curr[0] < max_y - 1 and (arr[curr[0] + 1][curr[1]] == '.' or arr[curr[0] + 1][curr[1]] == '*')) and (curr[0] + 1, curr[1]) not in tracker:
			inner_st.add((curr[0] + 1, curr[1]))
		if (curr[1] < max_x - 1 and (arr[curr[0]][curr[1] + 1] == '.' or arr[curr[0]][curr[1] + 1] == '*')) and (curr[0], curr[1] + 1) not in tracker:
			inner_st.add((curr[0], curr[1] + 1))
		if len(inner_st) > 1:
			tracker[curr] += 1
		for n in inner_st:
			tracker[n] = tracker[curr]
			st.append(n)
	return False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for line in range(n):
		a.append(list(input()))
	k = int(input())
	if hermionesWand(a, k, m, n):
		print('Impressed')
	else:
		print('Oops!')


import collections, sys

def search(map, start, finish, paths, waves):
	return
for case in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	map = []
	for i in range(n):
		map.append(input())
	k = int(input())
	graph = collections.defaultdict(set)
	for y in range(n):
		for x in range(m):
			if map[y][x] == 'M':
				pos_harmione = (x, y)
			if map[y][x] == '*':
				pos_target = (x, y)
			if map[y][x] != 'X':
				if y > 0:
					if map[y - 1][x] != 'X':
						graph[x, y].add((x, y - 1))
				if y < n - 1:
					if map[y + 1][x] != 'X':
						graph[x, y].add((x, y + 1))
				if x > 0:
					if map[y][x - 1] != 'X':
						graph[x, y].add((x - 1, y))
				if x < m - 1:
					if map[y][x + 1] != 'X':
						graph[x, y].add((x + 1, y))
	paths = collections.defaultdict(list)
	visited = set()
	frontier = [pos_harmione]
	while frontier:
		v = frontier.pop()
		visited.add(v)
		if v == pos_target:
			break
		for w in graph[v]:
			if w not in visited:
				frontier.append(w)
				paths[w] = paths[v] + [v]
	waves = 0
	for v in paths[pos_target]:
		if v == pos_harmione:
			if len(graph[v]) > 1:
				waves += 1
		elif len(graph[v]) > 2:
			waves += 1
	if waves == k:
		print('Impressed')
	else:
		print('Oops!')


class Node:

	def __init__(self, x, y, count):
		self.count = count
		self.x = x
		self.y = y

def move(x, y, graph, visited):
	places = []
	if len(graph) > x + 1 and graph[x + 1][y] in ['.', '*']:
		if (x + 1, y) not in visited:
			places.append([x + 1, y])
	if 0 <= x - 1 and graph[x - 1][y] in ['.', '*']:
		if (x - 1, y) not in visited:
			places.append([x - 1, y])
	if len(graph[0]) > y + 1 and graph[x][y + 1] in ['.', '*']:
		if (x, y + 1) not in visited:
			places.append([x, y + 1])
	if 0 <= y - 1 and graph[x][y - 1] in ['.', '*']:
		if (x, y - 1) not in visited:
			places.append([x, y - 1])
	return places

def make_move(pos, graph):
	to_visit = []
	visited = []
	to_visit.append(Node(pos[0], pos[1], 0))
	while to_visit:
		node = to_visit.pop()
		visited.append((node.x, node.y))
		if graph[node.x][node.y] == '*':
			return node.count
		available_moves = move(node.x, node.y, graph, visited)
		if len(available_moves) > 1:
			for pos in available_moves:
				to_visit.append(Node(pos[0], pos[1], node.count + 1))
		elif len(available_moves) == 1:
			to_visit.append(Node(available_moves[0][0], available_moves[0][1], node.count))

def find(graph):
	for x in range(len(graph)):
		for y in range(len(graph[x])):
			if graph[x][y] == 'M':
				return [x, y]
cases = int(input())
for i in range(cases):
	(height, width) = list(map(int, input().split()))
	graph = []
	for j in range(height):
		graph.append(input())
	if int(input()) == make_move(find(graph), graph):
		print('Impressed')
	else:
		print('Oops!')


from collections import defaultdict

def get_node(value, x, y, m):
	if value == 'M':
		return -1
	elif value == '*':
		return -2
	elif value == '.':
		return x * m + y + 1
	return None

def get_edges(values):
	edges = []
	n = len(values)
	m = len(values[0])
	for x in range(0, n):
		for y in range(0, m - 1):
			(a, b) = (values[x][y], values[x][y + 1])
			if a and b:
				edges.append((a, b))
	for x in range(0, n - 1):
		for y in range(0, m):
			(a, b) = (values[x][y], values[x + 1][y])
			if a and b:
				edges.append((a, b))
	path = defaultdict(list)
	for (x, y) in edges:
		path[x].append((x, y))
		path[y].append((y, x))
	return path

def find(path, start, end):
	crossing = 0
	p = []
	visited = set()
	visited.add(start)
	p.append(start)
	if len(path[start]) > 1:
		crossing += 1
	while len(p) > 0:
		if start == end:
			if len(path[start]) > 2:
				crossing -= 1
			return crossing
		for i in path[start]:
			(a, b) = i
			if b not in visited:
				start = b
				break
		if start in visited:
			if len(p) > 1 and len(path[start]) > 2:
				crossing -= 1
			p.pop()
			start = p[-1]
		else:
			visited.add(start)
			p.append(start)
			if len(path[start]) > 2:
				crossing += 1
	print('error')
t = int(input())
for i in range(0, t):
	(n, m) = [int(x) for x in input().split()]
	values = []
	for x in range(0, n):
		line = input()
		row = []
		for y in range(0, m):
			row.append(get_node(line[y], x, y, m))
		values.append(row)
	k = int(input())
	result = find(get_edges(values), -1, -2)
	print('Impressed' if result == k else 'Oops!')


from collections import namedtuple
p = namedtuple('p', 'i j')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g = [list(input()) for _ in range(n)]
	k = int(input())
	c = [p(i, j) for i in range(len(g)) for j in range(len(g[i])) if g[i][j] == 'M'][0]
	s = [c]
	w = set()
	while True:
		r = [p(c.i + i, c.j + j) for i in [-1, 0, 1] for j in [-1, 0, 1] if c.i + i >= 0 and c.i + i < n and (c.j + j >= 0) and (c.j + j < m) and (abs(i) != abs(j))]
		next = [x for x in r if g[x.i][x.j] == '.' or g[x.i][x.j] == '*']
		if len(next) > 1:
			w.add(c)
		check = [x for x in next if g[x.i][x.j] == '*']
		if len(check):
			break
		if len(next) > 0:
			c = next[0]
			s.append(c)
			g[c.i][c.j] = '+'
		else:
			s.pop()
			c = s[-1]
			if not len(s):
				break
	print('Impressed' if len(set(s) & w) == k else 'Oops!')


from collections import deque

class Forest(object):
	EMPTY = '.'
	TREE = 'X'
	EXIT = '*'
	HERMIONE = 'M'

	def __init__(self, width, height, grid):
		self.width = width
		self.height = height
		self.process(grid)

	@classmethod
	def from_input(cls, width, height):
		grid = []
		for _ in range(height):
			grid.append(input())
		return cls(width, height, grid)

	def process(self, grid):
		self.empty = set()
		self.tree = set()
		for (j, row) in enumerate(grid):
			for (i, cell) in enumerate(row):
				if cell == self.EMPTY:
					self.empty.add((j, i))
				elif cell == self.TREE:
					self.tree.add((j, i))
				elif cell == self.EXIT:
					self.exit = (j, i)
				elif cell == self.HERMIONE:
					self.start = (j, i)
				else:
					raise ValueError('Unknown marker {!r}'.format(cell))
		self.options = self.empty | set((self.start, self.exit))

	def get_options(self, coordinates):
		(j, i) = coordinates
		options = set(((j_, i_) for (j_, i_) in ((max(j - 1, 0), i), (min(j + 1, self.height - 1), i), (j, max(i - 1, 0)), (j, min(i + 1, self.width - 1))) if (j_, i_) in self.options and (j_, i_) != (j, i)))
		return options

	def find_path(self):
		turns = {}
		cells = deque([(self.start, 0)])
		while cells:
			(cell, turn) = cells.popleft()
			if cell in turns:
				continue
			turns[cell] = turn
			options = self.get_options(cell)
			for option in options:
				cells.append((option, turn + 1))
		cell = self.exit
		turn = turns[cell]
		path = deque([cell])
		while turn:
			turn -= 1
			for option in self.get_options(cell):
				if turns[option] == turn:
					cell = option
					path.appendleft(cell)
					break
		return list(path)

	def count_crossroads(self, path):
		count = 0
		start = path[0]
		path = path[1:-1]
		if len(self.get_options(start)) > 1:
			count += 1
		for cell in path:
			if len(self.get_options(cell)) - 1 > 1:
				count += 1
		return count
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	forest = Forest.from_input(width=M, height=N)
	K = int(input())
	path = forest.find_path()
	print('Impressed' if forest.count_crossroads(path) == K else 'Oops!')


def FindWaveNumber(matrix_size, matrix, current_node, visited_nodes, wave_count):
	if matrix[current_node[0]][current_node[1]] == '*':
		return [wave_count, True]
	visited_nodes.append(current_node)
	possible_paths = _DeterminePossiblePaths(matrix_size, matrix, current_node, visited_nodes)
	result = [0, False]
	if possible_paths[0]:
		if possible_paths[4]:
			result = FindWaveNumber(matrix_size, matrix, [current_node[0] - 1, current_node[1]], visited_nodes, wave_count + 1)
		else:
			result = FindWaveNumber(matrix_size, matrix, [current_node[0] - 1, current_node[1]], visited_nodes, wave_count)
		if result:
			return result
	if possible_paths[1]:
		if possible_paths[4]:
			result = FindWaveNumber(matrix_size, matrix, [current_node[0] + 1, current_node[1]], visited_nodes, wave_count + 1)
		else:
			result = FindWaveNumber(matrix_size, matrix, [current_node[0] + 1, current_node[1]], visited_nodes, wave_count)
		if result:
			return result
	if possible_paths[2]:
		if possible_paths[4]:
			result = FindWaveNumber(matrix_size, matrix, [current_node[0], current_node[1] - 1], visited_nodes, wave_count + 1)
		else:
			result = FindWaveNumber(matrix_size, matrix, [current_node[0], current_node[1] - 1], visited_nodes, wave_count)
		if result:
			return result
	if possible_paths[3]:
		if possible_paths[4]:
			result = FindWaveNumber(matrix_size, matrix, [current_node[0], current_node[1] + 1], visited_nodes, wave_count + 1)
		else:
			result = FindWaveNumber(matrix_size, matrix, [current_node[0], current_node[1] + 1], visited_nodes, wave_count)
		if result:
			return result

def _DetermineVisited(visited_nodes, new_node):
	for i in range(len(visited_nodes)):
		if new_node[0] == visited_nodes[i][0] and new_node[1] == visited_nodes[i][1]:
			return True
	return False

def _DeterminePossiblePaths(matrix_size, matrix, current_node, visited_nodes):
	possible_paths = [False for i in range(5)]
	possible_count = 0
	visited = _DetermineVisited(visited_nodes, [current_node[0] - 1, current_node[1]])
	if current_node[0] - 1 >= 0 and matrix[current_node[0] - 1][current_node[1]] != 'X' and (not visited):
		possible_paths[0] = True
		possible_count += 1
	visited = _DetermineVisited(visited_nodes, [current_node[0] + 1, current_node[1]])
	if current_node[0] + 1 < matrix_size[0] and matrix[current_node[0] + 1][current_node[1]] != 'X' and (not visited):
		possible_paths[1] = True
		possible_count += 1
	visited = _DetermineVisited(visited_nodes, [current_node[0], current_node[1] - 1])
	if current_node[1] - 1 >= 0 and matrix[current_node[0]][current_node[1] - 1] != 'X' and (not visited):
		possible_paths[2] = True
		possible_count += 1
	visited = _DetermineVisited(visited_nodes, [current_node[0], current_node[1] + 1])
	if current_node[1] + 1 < matrix_size[1] and matrix[current_node[0]][current_node[1] + 1] != 'X' and (not visited):
		possible_paths[3] = True
		possible_count += 1
	if possible_count > 1:
		possible_paths[4] = True
	return possible_paths
n = int(input())
for i in range(n):
	matrix_size = [int(i) for i in input().split()]
	matrix = []
	m_location = []
	for i in range(matrix_size[0]):
		matrix.append([])
		matrix_values = list(input())
		for j in range(matrix_size[1]):
			if matrix_values[j] == 'M':
				m_location.append(i)
				m_location.append(j)
			matrix[i].append(matrix_values[j])
	k = int(input())
	wave_num = FindWaveNumber(matrix_size, matrix, m_location, [], 0)[0]
	if wave_num == k:
		print('Impressed')
	else:
		print('Oops!')


from queue import *

class Node:

	def __init__(self, n, m, val):
		self.n = n
		self.m = m
		self.val = val
		self.neighbours = []
		self.parent = None
		self.visited = False

def get_id(n, m):
	return str(n) + ',' + str(m)
t = int(input())
for x in range(t):
	(N, M) = list(map(int, input().split()))
	forest = []
	for n in range(N):
		forest.append(input())
	nodes = {}
	for n in range(N):
		for m in range(M):
			val = forest[n][m]
			if val == 'X':
				continue
			id = get_id(n, m)
			if id not in nodes:
				nodes[id] = Node(n, m, val)
			thisNode = nodes[id]
			if val == 'M':
				start = thisNode
			if val == '*':
				end = thisNode
			if n - 1 >= 0 and forest[n - 1][m] != 'X':
				nID = get_id(n - 1, m)
				if nID not in nodes:
					nodes[nID] = Node(n - 1, m, forest[n - 1][m])
				thisNode.neighbours.append(nodes[nID])
			if n + 1 < N and forest[n + 1][m] != 'X':
				nID = get_id(n + 1, m)
				if nID not in nodes:
					nodes[nID] = Node(n + 1, m, forest[n + 1][m])
				thisNode.neighbours.append(nodes[nID])
			if m - 1 >= 0 and forest[n][m - 1] != 'X':
				nID = get_id(n, m - 1)
				if nID not in nodes:
					nodes[nID] = Node(n, m - 1, forest[n][m - 1])
				thisNode.neighbours.append(nodes[nID])
			if m + 1 < M and forest[n][m + 1] != 'X':
				nID = get_id(n, m + 1)
				if nID not in nodes:
					nodes[nID] = Node(n, m + 1, forest[n][m + 1])
				thisNode.neighbours.append(nodes[nID])
	q = Queue()
	q.put(start)
	while not q.empty():
		thisNode = q.get()
		if thisNode.val == '*':
			break
		if thisNode.visited:
			continue
		thisNode.visited = True
		for neighbour in thisNode.neighbours:
			if not neighbour.visited and neighbour.parent is None:
				neighbour.parent = thisNode
				q.put(neighbour)
	parent = end.parent
	k = 0
	while parent is not None:
		if parent.parent is not None and len(parent.neighbours) > 2:
			k += 1
		elif parent.parent is None and len(parent.neighbours) > 1:
			k += 1
		parent = parent.parent
	K = int(input())
	if k == K:
		print('Impressed')
	else:
		print('Oops!')


class ForbiddenForest:

	def __init__(self, forest):
		self.forest = forest
		self.waves = 0
		self.exit_found = False
		self.visited = set()

	def find_hermione(self):
		for i in range(len(self.forest)):
			j = self.forest[i].find('M')
			if j != -1:
				return (i, j)

	def next_cells(self, position):
		(i, j) = position
		moves = []
		if i - 1 >= 0 and self.forest[i - 1][j] != 'X' and ((i - 1, j) not in self.visited):
			moves.append((i - 1, j))
		if i + 1 < len(self.forest) and self.forest[i + 1][j] != 'X' and ((i + 1, j) not in self.visited):
			moves.append((i + 1, j))
		if j - 1 >= 0 and self.forest[i][j - 1] != 'X' and ((i, j - 1) not in self.visited):
			moves.append((i, j - 1))
		if j + 1 < len(self.forest[0]) and self.forest[i][j + 1] != 'X' and ((i, j + 1) not in self.visited):
			moves.append((i, j + 1))
		return moves

	def find_exit(self, position):
		self.visited.add(position)
		(i, j) = position
		if self.forest[i][j] == '*':
			self.exit_found = True
			return
		possible_moves = self.next_cells(position)
		if len(possible_moves) > 1:
			self.waves += 1
		for move in possible_moves:
			self.find_exit(move)
			if self.exit_found:
				return
		if len(possible_moves) > 1:
			self.waves -= 1
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	forest = tuple((input() for line in range(N)))
	K = int(input())
	f = ForbiddenForest(forest)
	start = f.find_hermione()
	f.find_exit(start)
	print('Impressed') if f.waves == K else print('Oops!')


import sys

class NoExitError(Exception):
	pass

def num_waves(forest, starting_point, last_point, exit_point):
	if starting_point[0] == exit_point[0] and starting_point[1] == exit_point[1]:
		return 0
	next_points = []
	for offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
		next_point = [starting_point[0] + offset[0], starting_point[1] + offset[1]]
		if 0 <= next_point[0] < len(forest) and 0 <= next_point[1] < len(forest[0]) and (forest[next_point[0]][next_point[1]] in ['.', '*']) and (last_point == None or next_point[0] != last_point[0] or next_point[1] != last_point[1]):
			next_points.append(next_point)
	if len(next_points) == 0:
		raise NoExitError()
	elif len(next_points) == 1:
		try:
			return num_waves(forest, next_points[0], starting_point, exit_point)
		except NoExitError:
			raise NoExitError()
	else:
		for p in next_points:
			try:
				return 1 + num_waves(forest, p, starting_point, exit_point)
			except NoExitError:
				pass
		raise NoExitError()
num_tests = int(sys.stdin.readline().rstrip())
for _ in range(num_tests):
	[n_rows, n_cols] = [int(n) for n in sys.stdin.readline().rstrip().split(' ')]
	forest = []
	starting_point = None
	exit_point = None
	for row_num in range(n_rows):
		row = list(sys.stdin.readline().rstrip())
		forest.append(row)
		if '*' in row:
			exit_point = [row_num, row.index('*')]
		if 'M' in row:
			starting_point = [row_num, row.index('M')]
	expected_num_waves = int(sys.stdin.readline().rstrip())
	actual_num_waves = num_waves(forest, starting_point, None, exit_point)
	if expected_num_waves == actual_num_waves:
		print('Impressed')
	else:
		print('Oops!')


from pprint import pprint
import sys

def is_empty(point):
	x = point[0]
	y = point[1]
	return forest[x][y] == 0

def can_move(point, forest):
	result = False
	x = point[0]
	lenx = len(forest)
	y = point[1]
	leny = len(forest[0])
	if x + 1 < lenx and forest[x + 1][y] == 0:
		result = True
	elif x - 1 >= 0 and forest[x - 1][y] == 0:
		result = True
	elif y + 1 < leny and forest[x][y + 1] == 0:
		result = True
	elif y - 1 >= 0 and forest[x][y - 1] == 0:
		result = True
	return result

def move(entry, forest, path):
	result = False
	row = entry[0]
	rows = len(forest)
	column = entry[1]
	current = ()
	columns = len(forest[0])
	if column + 1 < columns and forest[row][column + 1] == 0:
		current = (row, column + 1)
		result = True
	elif column - 1 >= 0 and forest[row][column - 1] == 0:
		current = (row, column - 1)
		result = True
	elif row + 1 < rows and forest[row + 1][column] == 0:
		current = (row + 1, column)
		result = True
	elif row - 1 >= 0 and forest[row - 1][column] == 0:
		current = (row - 1, column)
		result = True
	if result == True:
		path.append(current)
	return result

def is_crossroads(point, forest, start):
	row = point[0]
	column = point[1]
	rows = len(forest)
	columns = len(forest[0])
	if start == point:
		trigger = 2
	else:
		trigger = 3
	counter = 0
	if column + 1 < columns and forest[row][column + 1] != 2:
		counter += 1
	if column - 1 >= 0 and forest[row][column - 1] != 2:
		counter += 1
	if row + 1 < rows and forest[row + 1][column] != 2:
		counter += 1
	if row - 1 >= 0 and forest[row - 1][column] != 2:
		counter += 1
	return counter >= trigger

def traverse_forest(forest, start, end):
	row = start[0]
	column = start[1]
	path = []
	counter = 0
	backtrack = False
	path.append(start)
	while len(path) > 0:
		current_node = path[len(path) - 1]
		if current_node == end:
			break
		if is_crossroads(current_node, forest, start) and backtrack == False:
			counter += 1
		forest[current_node[0]][current_node[1]] = 1
		if not move(current_node, forest, path):
			path.pop()
			backtrack = True
			if is_crossroads(current_node, forest, start):
				counter -= 1
		else:
			backtrack = False
	return counter
test_size = int(sys.stdin.readline())
for i in range(test_size):
	start = ()
	end = ()
	(rows, columns) = map(int, sys.stdin.readline().split(' '))
	forest = [[0 for i in range(columns)] for j in range(rows)]
	for row_index in range(rows):
		line = sys.stdin.readline()
		for column_index in range(columns):
			if line[column_index] == 'X':
				forest[row_index][column_index] = 2
			elif line[column_index] == 'M':
				start = (row_index, column_index)
			elif line[column_index] == '*':
				end = (row_index, column_index)
	desired_count = int(sys.stdin.readline())
	result = traverse_forest(forest, start, end)
	if result == desired_count:
		print('Impressed')
	else:
		print('Oops!')


class TreeNode:

	def __init__(self, state, parent=None, children=[]):
		self.state = state
		self.parent = parent
		self.children = list(children)

def setupForestAndSearch():
	root = None
	(N, M) = [int(num) for num in input().split()]
	forest = []
	for i in range(N):
		forest.append(list(input()))
	K = int(input())
	for i in range(N):
		for j in range(M):
			if forest[i][j] == 'M':
				root = TreeNode((i, j))
				break
	frontier = [root]
	explored = set()
	while len(frontier) > 0:
		current = frontier.pop(0)
		explored.add(current)
		for action in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
			if current.state[0] + action[0] in range(N) and current.state[1] + action[1] in range(M) and (forest[current.state[0] + action[0]][current.state[1] + action[1]] in ['*', '.', 'M']):
				child = TreeNode((current.state[0] + action[0], current.state[1] + action[1]), current.state)
				if child.state not in [node.state for node in explored] and child.state not in [node.state for node in frontier]:
					if forest[child.state[0]][child.state[1]] == '*':
						backtrack_node = child
						path = [backtrack_node.state]
						(i, j) = (backtrack_node.state[0], backtrack_node.state[1])
						while forest[i][j] != 'M':
							parentNode = [node for node in explored if node.state == backtrack_node.parent][0]
							backtrack_node = parentNode
							path.append(parentNode.state)
							(i, j) = parentNode.state
						return (path, K, N, M, forest)
					frontier.append(child)
T = int(input())
for test in range(T):
	numWandWaves = 0
	(path, K, N, M, forest) = setupForestAndSearch()
	path = path[::-1][:-1]
	for (i, state) in enumerate(path):
		if len([(state[0] + action[0], state[1] + action[1]) for action in [(1, 0), (0, 1), (-1, 0), (0, -1)] if state[0] + action[0] in range(N) and state[1] + action[1] in range(M) and (forest[state[0] + action[0]][state[1] + action[1]] in ['*', '.']) and ((state[0] + action[0], state[1] + action[1]) not in path[:i])]) > 1:
			numWandWaves += 1
	print('Impressed' if numWandWaves == K else 'Oops!')


import sys
from collections import deque

def init():
	flag = False
	flag1 = False
	for i in range(n):
		for j in range(m):
			if a[i][j] == 'M':
				s1 = i
				s2 = j
				flag = True
			elif a[i][j] == '*':
				t1 = i
				t2 = j
				flag1 = True
			if flag and flag1:
				break
	return (s1, s2, t1, t2)

def dfs(s1, s2, t1, t2, v):
	cnt = 0
	if s1 == t1 and s2 == t2:
		return (True, cnt)
	c = 0
	flag = False
	v[s1][s2] = 1
	if s1 - 1 >= 0 and v[s1 - 1][s2] == 0 and (a[s1 - 1][s2] != 'X'):
		c = c + 1
		(flag1, cnt1) = dfs(s1 - 1, s2, t1, t2, v)
		if flag1:
			cnt = cnt + cnt1
		flag = flag | flag1
	if s1 + 1 <= n - 1 and v[s1 + 1][s2] == 0 and (a[s1 + 1][s2] != 'X'):
		c = c + 1
		(flag1, cnt1) = dfs(s1 + 1, s2, t1, t2, v)
		if flag1:
			cnt = cnt + cnt1
		flag = flag | flag1
	if s2 - 1 >= 0 and v[s1][s2 - 1] == 0 and (a[s1][s2 - 1] != 'X'):
		c = c + 1
		(flag1, cnt1) = dfs(s1, s2 - 1, t1, t2, v)
		if flag1:
			cnt = cnt + cnt1
		flag = flag | flag1
	if s2 + 1 <= m - 1 and v[s1][s2 + 1] == 0 and (a[s1][s2 + 1] != 'X'):
		c = c + 1
		(flag1, cnt1) = dfs(s1, s2 + 1, t1, t2, v)
		if flag1:
			cnt = cnt + cnt1
		flag = flag | flag1
	if flag and c > 1:
		cnt = cnt + 1
		return (True, cnt)
	elif flag and c <= 1:
		return (True, cnt)
	else:
		return (False, 1)
t = int(input().strip())
for i in range(t):
	(n, m) = [int(x) for x in input().strip().split()]
	a = [['' for i in range(m)] for j in range(n)]
	for j in range(n):
		a[j] = input().strip()
	k = int(input().strip())
	(i1, i2, j1, j2) = init()
	cnt = 0
	v = [[0 for j in range(m)] for i in range(n)]
	(f, cnt) = dfs(i1, i2, j1, j2, v)
	if cnt == k:
		print('Impressed')
	else:
		print('Oops!')


from collections import deque

def test():
	(y, x) = [int(x) for x in input().strip().split(' ')]
	data = []
	x_start = y_start = -1
	for i in range(y):
		data += [list(input().strip())]
		if 'M' in data[-1]:
			y_start = i
			x_start = data[-1].index('M')
	tries = int(input().strip())
	proc = deque()
	proc.append((y_start, x_start, 0, 0))
	while len(proc) > 0:
		(cur_y, cur_x, cur_desc, cur_steps) = proc.popleft()
		if data[cur_y][cur_x] == '*':
			if cur_desc == tries:
				print('Impressed')
			else:
				print('Oops!')
			return
		data[cur_y][cur_x] = 'Q'
		to_iter = []
		for step in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
			target_y = cur_y + step[0]
			target_x = cur_x + step[1]
			if target_y < 0 or target_x < 0 or target_y >= y or (target_x >= x):
				continue
			if data[target_y][target_x] in '.*':
				to_iter += [(target_y, target_x)]
		next_steps = cur_steps + 1
		next_desc = cur_desc
		if len(to_iter) > 1:
			next_desc = next_desc + 1
			data[cur_y][cur_x] = 'D'
		for next_step in to_iter:
			proc.append((next_step[0], next_step[1], next_desc, next_steps))
	print('Oops!')
	tries = int(input().strip())
	print(x_start, y_start)
	print(data)
x = int(input().strip())
for i in range(x):
	test()


ar = []
m = 0
n = 0

def path(x, y, K, t, u):
	connected = 1
	if count(x, y) > 2:
		K += 1
	l = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
	for (i, j) in l:
		if i > -1 and i < m and (j > -1) and (j < n) and ((i, j) != (t, u)):
			if ar[i][j] == '.':
				ans = path(i, j, K, x, y)
				if ans != -1:
					return ans
			if ar[i][j] == '*':
				return K
	return -1

def count(x, y):
	meep = 0
	l = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
	for (i, j) in l:
		if i > -1 and i < m and (j > -1) and (j < n):
			if ar[i][j] != 'X':
				meep += 1
	return meep

def find(ar):
	for i in range(m):
		for j in range(n):
			if ar[i][j] == 'M':
				return (i, j)
T = int(input())
for T_i in range(T):
	K = 0
	ar = []
	(m, n) = [int(x) for x in input().split()]
	for i in range(m):
		row = [x for x in input()]
		rows = [0 for x in row]
		ar.append(row)
	(x, y) = find(ar)
	if count(x, y) == 2:
		K = 1
	ans = path(x, y, K, -1, -1)
	look = int(input())
	if look != ans:
		print('Oops!')
	else:
		print('Impressed')


def pf(forest):
	for i in forest:
		print(i)
dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

def dfs(forest, mx, my, sx, sy, k=0):
	if forest[sy][sx] == '*':
		return k
	forest[sy][sx] = 'X'
	allowed = []
	for i in dirs:
		px = sx + i[0]
		py = sy + i[1]
		if px >= 0 and py >= 0 and (px < mx) and (py < my) and (forest[py][px] != 'X'):
			allowed.append((px, py))
	if len(allowed) > 1:
		k = k + 1
	for i in allowed:
		ret = dfs(forest, mx, my, i[0], i[1], k)
		if ret != None:
			return ret
	return None
T = int(input())
while T:
	T = T - 1
	(N, M) = [int(i) for i in input().split()]
	forest = []
	for i in range(N):
		forest.append([i for i in input()])
	K = int(input())
	for y in range(N):
		for x in range(M):
			if forest[y][x] == 'M':
				start = [x, y]
	k = dfs(forest, M, N, start[0], start[1])
	if k == K:
		print('Impressed')
	else:
		print('Oops!')


def nbrs(n, m, N, M):
	return_val = []
	if n != 0:
		return_val.append((n - 1, m))
	if m != 0:
		return_val.append((n, m - 1))
	if n != N - 1:
		return_val.append((n + 1, m))
	if m != M - 1:
		return_val.append((n, m + 1))
	return return_val

def needs_wand(matrix, n, m, N, M):
	non_x_count = 0
	for (new_n, new_m) in nbrs(n, m, N, M):
		if matrix[new_n][new_m] != 'X':
			non_x_count += 1
	return non_x_count

def find_start(matrix, n, m, N, M):
	K = int(input())
	k_count = 0
	while True:
		wand_count = needs_wand(matrix, n, m, N, M)
		if matrix[n][m] == 'M':
			if wand_count > 1:
				k_count += 1
			print('Impressed' if k_count == K else 'Oops!')
			break
		else:
			if wand_count > 2:
				k_count += 1
			(n, m) = matrix[n][m]

def run():
	(N, M) = [int(x) for x in input().split()]
	matrix = []
	to_search = []
	for n in range(N):
		matrix.append(list(input()))
		for m in range(M):
			if matrix[n][m] == 'M':
				to_search.append((n, m))
	while to_search[0] != '*':
		(n, m) = to_search.pop(0)
		cell = matrix[n][m]
		for (new_n, new_m) in nbrs(n, m, N, M):
			if matrix[new_n][new_m] == '.':
				matrix[new_n][new_m] = (n, m)
				to_search.append((new_n, new_m))
			elif matrix[new_n][new_m] == '*':
				return find_start(matrix, n, m, N, M)
for _ in range(int(input())):
	run()


def countLuck(l, N, M, K):
	visited = list()
	visitedTrack = list()
	startVertex = tuple()
	endVertex = tuple()
	wandUsed = 0
	for i in range(N):
		for j in range(M):
			if l[i][j] == 'M':
				startVertex = (i, j)
			if l[i][j] == '*':
				endVertex = (i, j)
	visited.append(startVertex)
	while visited:
		curr = visited.pop()
		visitedTrack.append(curr)
		track = list()
		if curr == endVertex:
			return wandUsed == K
		if curr[1] > 0 and (l[curr[0]][curr[1] - 1] == '.' or l[curr[0]][curr[1] - 1] == '*') and ((curr[0], curr[1] - 1) not in visitedTrack):
			vertex = (curr[0], curr[1] - 1)
			track.append(vertex)
		if curr[0] < N - 1 and (l[curr[0] + 1][curr[1]] == '.' or l[curr[0] + 1][curr[1]] == '*') and ((curr[0] + 1, curr[1]) not in visitedTrack):
			vertex = (curr[0] + 1, curr[1])
			track.append(vertex)
		if curr[0] > 0 and (l[curr[0] - 1][curr[1]] == '.' or l[curr[0] - 1][curr[1]] == '*') and ((curr[0] - 1, curr[1]) not in visitedTrack):
			vertex = (curr[0] - 1, curr[1])
			track.append(vertex)
		if curr[1] < M - 1 and (l[curr[0]][curr[1] + 1] == '.' or l[curr[0]][curr[1] + 1] == '*') and ((curr[0], curr[1] + 1) not in visitedTrack):
			vertex = (curr[0], curr[1] + 1)
			track.append(vertex)
		if len(track) > 1:
			wandUsed = wandUsed + 1
		for i in range(len(track)):
			visited.append(track[i])
	return False
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	l = list()
	for j in range(N):
		l.append(list(input()))
	K = int(input())
	if countLuck(l, N, M, K):
		print('Impressed')
	else:
		print('Oops!')


T = int(input())

def is_empty(board, p):
	return board[p[0]][p[1]] in ['.', '*']

def get_children(board, i, j, visited):
	res = []
	if j > 0:
		res.append((i, j - 1))
	if j < len(board[0]) - 1:
		res.append((i, j + 1))
	if i > 0:
		res.append((i - 1, j))
	if i < len(board) - 1:
		res.append((i + 1, j))
	return [p for p in res if is_empty(board, p) and (not visited[p[0]][p[1]])]

def dfs(board, i, j, res, visited):
	visited[i][j] = True
	if board[i][j] == '*':
		return True
	children = get_children(board, i, j, visited)
	if len(children) > 1:
		res[0] += 1
	for child in children:
		if not visited[child[0]][child[1]]:
			if dfs(board, child[0], child[1], res, visited):
				return True
	if len(children) > 1:
		res[0] -= 1
	return False

def solve():
	(N, M) = [int(i) for i in input().split(' ')]
	board = []
	s = None
	t = None
	for i in range(N):
		board.append(list(input()))
		if not s and 'M' in board[i]:
			s = (i, board[i].index('M'))
	K = int(input())
	visited = [[0 for j in range(M)] for i in range(N)]
	res = [0]
	dfs(board, s[0], s[1], res, visited)
	if res[0] == K:
		print('Impressed')
	else:
		print('Oops!')
for i in range(T):
	solve()


VALID = '.'
START = 'M'
END = '*'
VALID_SQUARES = VALID + START + END
INVALID = 'X'
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))

def add_tuples(a, b):
	return tuple([x + y for (x, y) in zip(a, b)])

def valid_squares(pos, game_map):
	count = 0
	for direction in directions:
		new_pos = add_tuples(pos, direction)
		(x, y) = new_pos
		if 0 <= x < len(game_map[0]) and 0 <= y < len(game_map):
			if game_map[y][x] != INVALID:
				count += 1
	return count

def dfs(start, end, game_map):
	path = [()]
	starting_waves = 0
	if valid_squares(start, game_map) >= 2:
		starting_waves = 1
		path = [start]
	stack = [(start, starting_waves)]
	visited = set()
	while stack:
		(square, waves) = stack.pop()
		c_path = path.pop()
		if square in visited:
			continue
		visited.add(square)
		if square == end:
			return waves
		for direction in directions:
			new_square = add_tuples(square, direction)
			(x, y) = new_square
			if 0 <= x < len(game_map[0]) and 0 <= y < len(game_map):
				if game_map[y][x] != INVALID:
					if valid_squares(new_square, game_map) > 2 and game_map[y][x] != END:
						stack.append((new_square, waves + 1))
						path.append(c_path + new_square)
					else:
						stack.append((new_square, waves))
						path.append(c_path)
	return 0
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	forest = []
	for _ in range(n):
		forest.append(input())
	k = int(input())
	start = -1
	end = -1
	for (y, f_l) in enumerate(forest):
		if start == -1:
			start = f_l.find(START)
			if start != -1:
				start = (start, y)
		if end == -1:
			end = f_l.find(END)
			if end != -1:
				end = (end, y)
	waves = dfs(start, end, forest)
	print('Impressed' if waves == k else 'Oops!')


di = [0, 0, 1, -1]
dj = [1, -1, 0, 0]

def calculate(matrix, K):
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			if matrix[i][j] == 'M':
				start = (i, j, 0)
	stack = [start]
	visited = set()
	while stack:
		(current_i, current_j, counter) = stack.pop()
		if (current_i, current_j) in visited:
			continue
		if matrix[current_i][current_j] == '*':
			result = counter
			break
		visited.add((current_i, current_j))
		moves = []
		for k in range(4):
			(candidate_i, candidate_j) = (current_i + di[k], current_j + dj[k])
			if (candidate_i, candidate_j) not in visited and (candidate_i >= 0 and candidate_i < len(matrix)) and (candidate_j >= 0 and candidate_j < len(matrix[0])) and (matrix[candidate_i][candidate_j] != 'X'):
				moves.append((candidate_i, candidate_j))
		if not moves:
			continue
		for move in moves:
			stack.append((move[0], move[1], counter + 1 if len(moves) > 1 else counter))
	return result == K

def actions():
	while True:
		yield input()
go = actions()
T = int(next(go))
for i in range(T):
	(n, m) = [int(i) for i in next(go).split()]
	matrix = []
	for i in range(n):
		matrix.append(next(go))
	k = int(next(go))
	print('Impressed' if calculate(matrix, k) else 'Oops!')


from enum import Enum

class Dir(Enum):
	right = (1, 0)
	down = (0, 1)
	left = (-1, 0)
	up = (0, -1)

def find_start_pos(array):
	for y in range(len(array)):
		for x in range(len(array[i])):
			if array[y][x] == 'M':
				return (x, y)

def move(x, y, x_max, y_max, array, count):
	dirs = []
	if array[y][x] == '*':
		return count
	else:
		if x < x_max and array[y][x + 1] != 'X':
			dirs.append(Dir.right)
		if y < y_max and array[y + 1][x] != 'X':
			dirs.append(Dir.down)
		if x > 0 and array[y][x - 1] != 'X':
			dirs.append(Dir.left)
		if y > 0 and array[y - 1][x] != 'X':
			dirs.append(Dir.up)
		array[y][x] = 'X'
		if len(dirs) > 1:
			count += 1
		elif len(dirs) == 0:
			return -1
		for d in dirs:
			(dir_x, dir_y) = d.value
			way = move(x + dir_x, y + dir_y, x_max, y_max, array, count)
			if way != -1:
				return way
		return -1
nb_test = int(input())
for t in range(nb_test):
	(lines, raws) = [int(x) for x in input().split()]
	array = []
	for i in range(lines):
		array.append([])
	for i in range(lines):
		array[i] = [x for x in input()]
	(x, y) = find_start_pos(array)
	count = move(x, y, raws - 1, lines - 1, array, 0)
	expected = int(input())
	if expected == count:
		print('Impressed')
	else:
		print('Oops!')


def findPath(parent, start, target):
	path = []
	baap = target
	while baap != None:
		path.append(baap)
		baap = parent[baap]
	return path

def bfs(start, target, adjMatrix):
	parent = {}
	que = []
	que.append(start)
	parent[start] = None
	while len(que) > 0:
		current = que.pop(0)
		if current == target:
			return parent
		for neig in adjMatrix[current]:
			if neig not in parent:
				que.append(neig)
				parent[neig] = current
testcases = int(input())
for _ in range(testcases):
	size = input().split()
	graph = {}
	adjMatrix = {}
	for counter in range(int(size[0])):
		row = input()
		for innerCounter in range(int(size[1])):
			if row[innerCounter] in ['.', '*', 'M']:
				graph[tuple([counter, innerCounter])] = True
				if row[innerCounter] == '*':
					target = tuple([counter, innerCounter])
				if row[innerCounter] == 'M':
					start = tuple([counter, innerCounter])
	expected = input()
	for row in range(int(size[0])):
		for cal in range(int(size[1])):
			if tuple([row, cal]) in graph:
				adjMatrix[tuple([row, cal])] = []
				if tuple([row + 1, cal]) in graph:
					adjMatrix[tuple([row, cal])].append(tuple([row + 1, cal]))
				if tuple([row - 1, cal]) in graph:
					adjMatrix[tuple([row, cal])].append(tuple([row - 1, cal]))
				if tuple([row, cal - 1]) in graph:
					adjMatrix[tuple([row, cal])].append(tuple([row, cal - 1]))
				if tuple([row, cal + 1]) in graph:
					adjMatrix[tuple([row, cal])].append(tuple([row, cal + 1]))
	parent = bfs(start, target, adjMatrix)
	path = findPath(parent, start, target)
	wave = 0
	for item in path:
		if item == start and len(adjMatrix[item]) > 1:
			wave += 1
		elif item != target and len(adjMatrix[item]) > 2:
			wave += 1
	if wave == int(expected):
		print('Impressed')
	else:
		print('Oops!')


def Traverse(a, paths, y, x, visited, target):
	visited.add((y, x))
	if (y, x) == target:
		return
	if a[y + 1][x] == 0 and (y + 1, x) not in visited:
		paths[y + 1][x] = (y, x)
		Traverse(a, paths, y + 1, x, visited, target)
	if a[y - 1][x] == 0 and (y - 1, x) not in visited:
		paths[y - 1][x] = (y, x)
		Traverse(a, paths, y - 1, x, visited, target)
	if a[y][x + 1] == 0 and (y, x + 1) not in visited:
		paths[y][x + 1] = (y, x)
		Traverse(a, paths, y, x + 1, visited, target)
	if a[y][x - 1] == 0 and (y, x - 1) not in visited:
		paths[y][x - 1] = (y, x)
		Traverse(a, paths, y, x - 1, visited, target)
t = int(input())
for test in range(t):
	(N, M) = map(int, input().split())
	a = [[1] * (M + 2) for _ in range(N + 2)]
	target_y = target_x = start_y = start_x = -1
	for n in range(1, N + 1):
		s = input()
		for k in range(len(s)):
			if s[k] == '.':
				a[n][k + 1] = 0
			if s[k] == 'X':
				a[n][k + 1] = 1
			if s[k] == 'M':
				a[n][k + 1] = 0
				start_y = n
				start_x = k + 1
			if s[k] == '*':
				a[n][k + 1] = 0
				target_y = n
				target_x = k + 1
	K = int(input())
	res = 0
	paths = [[(-1, -1)] * (M + 2) for _ in range(N + 2)]
	Traverse(a, paths, start_y, start_x, set(), (target_y, target_x))
	y = target_y
	x = target_x
	while paths[y][x] != (start_y, start_x):
		(y, x) = (paths[y][x][0], paths[y][x][1])
		res += a[y + 1][x] + a[y - 1][x] + a[y][x + 1] + a[y][x - 1] < 2
	res += a[start_y + 1][start_x] + a[start_y - 1][start_x] + a[start_y][start_x + 1] + a[start_y][start_x - 1] < 3
	print('Impressed' if res == K else 'Oops!')


vis_places = None

def check_loc(vis_places, x, y, start):
	cnt = 0
	if y > 0 and vis_places[y - 1][x] != 0:
		cnt += 1
	if y < H - 1 and vis_places[y + 1][x] != 0:
		cnt += 1
	if x < W - 1 and vis_places[y][x + 1] != 0:
		cnt += 1
	if x > 0 and vis_places[y][x - 1] != 0:
		cnt += 1
	if start:
		cnt += 1
	if cnt >= 3:
		return 1
	return 0

def find_path(H, W, forest, L, start_pos, fin_pos):
	global vis_places
	vis_places[start_pos[0]][start_pos[1]] = 1
	next_pos = []
	next_pos.append(start_pos)
	while fin_pos not in next_pos:
		curr_pos = next_pos
		next_pos = []
		for pos in curr_pos:
			y = pos[0]
			x = pos[1]
			if y > 0 and forest[y - 1][x] in ['.', '*'] and (vis_places[y - 1][x] == 0):
				next_pos.append((y - 1, x))
				vis_places[y - 1][x] = vis_places[y][x] + 1
			if y < H - 1 and forest[y + 1][x] in ['.', '*'] and (vis_places[y + 1][x] == 0):
				next_pos.append((y + 1, x))
				vis_places[y + 1][x] = vis_places[y][x] + 1
			if x < W - 1 and forest[y][x + 1] in ['.', '*'] and (vis_places[y][x + 1] == 0):
				next_pos.append((y, x + 1))
				vis_places[y][x + 1] = vis_places[y][x] + 1
			if x > 0 and forest[y][x - 1] in ['.', '*'] and (vis_places[y][x - 1] == 0):
				next_pos.append((y, x - 1))
				vis_places[y][x - 1] = vis_places[y][x] + 1
	path = []
	curr_pos = fin_pos
	for i in range(vis_places[fin_pos[0]][fin_pos[1]] - 1, 0, -1):
		x = curr_pos[1]
		y = curr_pos[0]
		if x > 0 and vis_places[y][x - 1] == i:
			curr_pos = (y, x - 1)
			path.append(curr_pos)
			if curr_pos == start_pos:
				break
			continue
		if x < W - 1 and vis_places[y][x + 1] == i:
			curr_pos = (y, x + 1)
			path.append(curr_pos)
			if curr_pos == start_pos:
				break
			continue
		if y > 0 and vis_places[y - 1][x] == i:
			curr_pos = (y - 1, x)
			path.append(curr_pos)
			if curr_pos == start_pos:
				break
			continue
		if y < H - 1 and vis_places[y + 1][x] == i:
			curr_pos = (y + 1, x)
			path.append(curr_pos)
			if curr_pos == start_pos:
				break
			continue
	res = sum([check_loc(vis_places, dot[1], dot[0], dot == start_pos) for dot in path])
	return res

def test_case(H, W, forest, L, start_pos, fin_pos):
	global vis_places
	vis_places = [[0 for _ in range(W)] for __ in range(H)]
	res = ['Impressed', 'Oops!']
	res_ = find_path(H, W, forest, L, start_pos, fin_pos)
	if L == res_:
		return res[0]
	return res[1]
T = int(input().strip())
for _ in range(T):
	(H, W) = map(int, input().strip().split())
	forest = []
	for i in range(H):
		forest.append(input().strip())
		if '*' in forest[-1]:
			fin_pos = (i, forest[-1].index('*'))
		if 'M' in forest[-1]:
			start_pos = (i, forest[-1].index('M'))
	L = int(input().strip())
	print(test_case(H, W, forest, L, start_pos, fin_pos))


def search(g, m, n, i, j, c=0):
	if g[i][j] == '*':
		return c
	g[i][j] = 0
	moves = getmoves(g, m, n, i, j)
	if len(moves) > 1:
		c += 1
	for mv in moves:
		res = search(g, m, n, mv[0], mv[1], c)
		if res != None:
			return res
	return None

def getmoves(g, m, n, i, j):
	(l, v) = ([], ('.', '*'))
	if i > 0 and g[i - 1][j] in v:
		l.append((i - 1, j))
	if j > 0 and g[i][j - 1] in v:
		l.append((i, j - 1))
	if i < m - 1 and g[i + 1][j] in v:
		l.append((i + 1, j))
	if j < n - 1 and g[i][j + 1] in v:
		l.append((i, j + 1))
	return l
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	g = [list(input()) for _ in range(m)]
	k = int(input())
	for i in range(m):
		for j in range(n):
			if g[i][j] == 'M':
				print('Impressed' if search(g, m, n, i, j) == k else 'Oops!')
				break


t = int(input())

def path(l, hr, hc, k, k1, n, m, ohr, ohc):
	if hr + 1 < n and hr + 1 != ohr and (l[hr + 1][hc] == '.' or l[hr + 1][hc] == '*') and (hr - 1 >= 0) and (hr - 1 != ohr) and (l[hr - 1][hc] == '.' or l[hr - 1][hc] == '*'):
		k1 += 1
	elif hr + 1 < n and hr + 1 != ohr and (l[hr + 1][hc] == '.' or l[hr + 1][hc] == '*') and (hc + 1 < m) and (hc + 1 != ohc) and (l[hr][hc + 1] == '.' or l[hr][hc + 1] == '*'):
		k1 += 1
	elif hr + 1 < n and hr + 1 != ohr and (l[hr + 1][hc] == '.' or l[hr + 1][hc] == '*') and (hc - 1 >= 0) and (hc - 1 != ohc) and (l[hr][hc - 1] == '.' or l[hr][hc - 1] == '*'):
		k1 += 1
	elif hr - 1 >= 0 and hr - 1 != ohr and (l[hr - 1][hc] == '.' or l[hr - 1][hc] == '*') and (hc + 1 < m) and (hc + 1 != ohc) and (l[hr][hc + 1] == '.' or l[hr][hc + 1] == '*'):
		k1 += 1
	elif hr - 1 >= 0 and hr - 1 != ohr and (l[hr - 1][hc] == '.' or l[hr - 1][hc] == '*') and (hc - 1 >= 0) and (hc - 1 != ohc) and (l[hr][hc - 1] == '.' or l[hr][hc - 1] == '*'):
		k1 += 1
	elif hc + 1 < m and hc + 1 != ohc and (l[hr][hc + 1] == '.' or l[hr][hc + 1] == '*') and (hc - 1 >= 0) and (hc - 1 != ohc) and (l[hr][hc - 1] == '.' or l[hr][hc - 1] == '*'):
		k1 += 1
	if hr - 1 >= 0 and l[hr - 1][hc] == '.' and (hr - 1 != ohr):
		l[hr - 1][hc] = 'M'
		l[hr][hc] = '.'
		path(l, hr - 1, hc, k, k1, n, m, hr, hc)
	if hr + 1 < n and l[hr + 1][hc] == '.' and (hr + 1 != ohr):
		l[hr + 1][hc] = 'M'
		l[hr][hc] = '.'
		path(l, hr + 1, hc, k, k1, n, m, hr, hc)
	if hc - 1 >= 0 and l[hr][hc - 1] == '.' and (hc - 1 != ohc):
		l[hr][hc - 1] = 'M'
		l[hr][hc] = '.'
		path(l, hr, hc - 1, k, k1, n, m, hr, hc)
	if hc + 1 < m and l[hr][hc + 1] == '.' and (hc + 1 != ohc):
		l[hr][hc + 1] = 'M'
		l[hr][hc] = '.'
		path(l, hr, hc + 1, k, k1, n, m, hr, hc)
	if hr - 1 >= 0 and l[hr - 1][hc] == '*':
		if k1 == k:
			print('Impressed')
		else:
			print('Oops!')
	elif hr + 1 < n and l[hr + 1][hc] == '*':
		if k1 == k:
			print('Impressed')
		else:
			print('Oops!')
	elif hc - 1 >= 0 and l[hr][hc - 1] == '*':
		if k1 == k:
			print('Impressed')
		else:
			print('Oops!')
	elif hc + 1 < m and l[hr][hc + 1] == '*':
		if k1 == k:
			print('Impressed')
		else:
			print('Oops!')
for i in range(t):
	l = []
	h = []
	n = input().split()
	m = int(n[1])
	n = int(n[0])
	for j in range(n):
		li = []
		s = input()
		if 'M' in s:
			h.append(j)
			h.append(s.find('M'))
		for k in s:
			li.append(k)
		l.append(li)
	k = int(input())
	k1 = 0
	path(l, h[0], h[1], k, k1, n, m, h[0], h[1])


class Node:

	def __init__(self, x, y, waves=-1):
		self.x = x
		self.y = y
		self.waves = waves

	def __str__(self):
		return '<x:%s y:%s w:%s>' % (self.x, self.y, self.waves)
	__repr__ = __str__

def get_neighbours(grid, node):
	neighbours = []
	x = node.x
	y = node.y
	if x > 0 and grid[x - 1][y]:
		neighbours.append(grid[x - 1][y])
	if x < len(grid) - 1 and grid[x + 1][y]:
		neighbours.append(grid[x + 1][y])
	if y > 0 and grid[x][y - 1]:
		neighbours.append(grid[x][y - 1])
	if y < len(grid[0]) - 1 and grid[x][y + 1]:
		neighbours.append(grid[x][y + 1])
	return neighbours

def search(grid, start, dest):
	stack = list()
	stack.append(start)
	while stack:
		node = stack.pop(-1)
		neighbours = get_neighbours(grid, node)
		neighbours = [x for x in neighbours if x.waves == -1]
		if node.x == dest.x and node.y == dest.y:
			return node.waves
		need_wave = 1 if len(neighbours) > 1 else 0
		node.waves = node.waves + need_wave if node.waves != -1 else need_wave
		for neighbour in neighbours:
			if neighbour.waves == -1:
				neighbour.waves = node.waves
				stack.append(neighbour)
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().strip().split())
	board = [input() for _ in range(N)]
	K = int(input())
	grid = []
	for i in range(N):
		grid.append([Node(i, j) if board[i][j] != 'X' else None for j in range(M)])
		for j in range(M):
			if board[i][j] == '*':
				dest = grid[i][j]
			elif board[i][j] == 'M':
				start = grid[i][j]
	print('Impressed' if K == search(grid, start, dest) else 'Oops!')


def get_neighbors(node, node_set):
	return [n for n in ((node[0] - 1, node[1]), (node[0] + 1, node[1]), (node[0], node[1] + 1), (node[0], node[1] - 1)) if n in node_set]
res_map = {True: 'Impressed', False: 'Oops!'}
t = int(input().strip())
for _ in range(t):
	(n, m) = map(int, input().strip().split(' '))
	nodes = [(i, j, label) for i in range(n) for (j, label) in enumerate(input().strip()) if label != 'X']
	root = None
	exit = None
	node_points = set(((x, y) for (x, y, _) in nodes))
	for (x, y, label) in nodes:
		if label == 'M':
			root = (x, y)
		if label == '*':
			exit = (x, y)
	assert root is not None
	assert exit is not None
	k = int(input().strip())
	wand_waves = 0
	visited = set()
	todo = [(root, wand_waves)]
	while todo:
		(node, wand_waves) = todo.pop()
		if node == exit:
			break
		neighbors = [node_ for node_ in get_neighbors(node, node_points) if node_ not in visited]
		if len(neighbors) > 1:
			wand_waves += 1
		for node_ in neighbors:
			todo.insert(0, (node_, wand_waves))
		visited.add(node)
	print(res_map[wand_waves == k])


case_number = int(input().strip())

def get_paths_with_dfs(graph, start, goal, path):
	if start == goal:
		yield path
	for next in graph[start] - set(path):
		yield from get_paths_with_dfs(graph, next, goal, path + [next])
for _ in range(case_number):
	(n, m) = input().strip().split(' ')
	(n_size, m_size) = (int(n), int(m))
	matrix = [['X'] * (m_size + 2)]
	ind = 1
	for index in range(n_size):
		new_line = ['X']
		for elem in input().strip():
			if elem == '.':
				new_line.append(ind)
				ind += 1
			elif elem == '*':
				new_line.append(ind)
				final_point = ind
				ind += 1
			elif elem == 'M':
				new_line.append(ind)
				start_point = ind
				ind += 1
			else:
				new_line.append('X')
		new_line.append('X')
		matrix.append(new_line)
	matrix.append(['X'] * (m_size + 2))
	k_size = int(input().strip())
	graph = {}
	for i_index in range(n_size):
		for j_index in range(m_size):
			elem = matrix[1 + i_index][1 + j_index]
			if type(elem) == int:
				graph[elem] = set()
				left_elem = matrix[1 + i_index][j_index]
				right_elem = matrix[1 + i_index][j_index + 2]
				top_elem = matrix[i_index][1 + j_index]
				bottom_elem = matrix[i_index + 2][j_index + 1]
				for elem_to_compare in (left_elem, right_elem, top_elem, bottom_elem):
					if type(elem_to_compare) == int:
						graph[elem].add(elem_to_compare)
	paths = list(get_paths_with_dfs(graph, start_point, final_point, [start_point]))
	waves = 0
	assert len(paths) == 1
	path = paths[0]
	cur_path = []
	for vertix in path[:-1]:
		cur_path += [vertix]
		neighbours = graph[vertix]
		variants = list(set(neighbours) - set(cur_path))
		if len(variants) > 1:
			waves += 1
	if waves == k_size:
		print('Impressed')
	else:
		print('Oops!')