You are an all-powerful being and you have created a rectangular world. In fact, your world is so bland that it could be represented by a $r \times c$ grid. Each cell on the grid represents a country. Each country has a dominant religion. There are only two religions in your world. One of the religions is called Beingawesomeism, who do good for the sake of being good. The other religion is called Pushingittoofarism, who do murders for the sake of being bad.

Oh, and you are actually not really all-powerful. You just have one power, which you can use infinitely many times! Your power involves missionary groups. When a missionary group of a certain country, say $a$, passes by another country $b$, they change the dominant religion of country $b$ to the dominant religion of country $a$.

In particular, a single use of your power is this:   You choose a horizontal $1 \times x$ subgrid or a vertical $x \times 1$ subgrid. That value of $x$ is up to you;  You choose a direction $d$. If you chose a horizontal subgrid, your choices will either be NORTH or SOUTH. If you choose a vertical subgrid, your choices will either be EAST or WEST;  You choose the number $s$ of steps;  You command each country in the subgrid to send a missionary group that will travel $s$ steps towards direction $d$. In each step, they will visit (and in effect convert the dominant religion of) all $s$ countries they pass through, as detailed above.  The parameters $x$, $d$, $s$ must be chosen in such a way that any of the missionary groups won't leave the grid. 

The following image illustrates one possible single usage of your power. Here, A represents a country with dominant religion Beingawesomeism and P represents a country with dominant religion Pushingittoofarism. Here, we've chosen a $1 \times 4$ subgrid, the direction NORTH, and $s = 2$ steps.  [Image] 

You are a being which believes in free will, for the most part. However, you just really want to stop receiving murders that are attributed to your name. Hence, you decide to use your powers and try to make Beingawesomeism the dominant religion in every country.

What is the minimum number of usages of your power needed to convert everyone to Beingawesomeism?

With god, nothing is impossible. But maybe you're not god? If it is impossible to make Beingawesomeism the dominant religion in all countries, you must also admit your mortality and say so.


-----Input-----

The first line of input contains a single integer $t$ ($1 \le t \le 2\cdot 10^4$) denoting the number of test cases.

The first line of each test case contains two space-separated integers $r$ and $c$ denoting the dimensions of the grid ($1 \le r, c \le 60$). The next $r$ lines each contains $c$ characters describing the dominant religions in the countries. In particular, the $j$-th character in the $i$-th line describes the dominant religion in the country at the cell with row $i$ and column $j$, where:  "A" means that the dominant religion is Beingawesomeism;  "P" means that the dominant religion is Pushingittoofarism. 

It is guaranteed that the grid will only contain "A" or "P" characters. It is guaranteed that the sum of the $r \cdot c$ in a single file is at most $3 \cdot 10^6$.


-----Output-----

For each test case, output a single line containing the minimum number of usages of your power needed to convert everyone to Beingawesomeism, or the string "MORTAL" (without quotes) if it is impossible to do so. 


-----Example-----
Input
4
7 8
AAPAAAAA
PPPPAAAA
PPPPAAAA
APAAPPPP
APAPPAPP
AAAAPPAP
AAAAPPAA
6 5
AAAAA
AAAAA
AAPAA
AAPAP
AAAPP
AAAPP
4 4
PPPP
PPPP
PPPP
PPPP
3 4
PPPP
PAAP
PPPP

Output
2
1
MORTAL
4



-----Note-----

In the first test case, it can be done in two usages, as follows:

Usage 1: [Image] 

Usage 2: [Image] 

In the second test case, it can be done with just one usage of the power. 

In the third test case, it is impossible to convert everyone to Beingawesomeism, so the answer is "MORTAL".

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

Implementation


Solutions:
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(h, w) = list(map(int, input().split()))
	grid = []
	for _ in range(h):
		line = input().rstrip('\n')
		tmp = [line[i] == 'A' for i in range(w)]
		grid.append(tmp)
	ok = 0
	all_A = 1
	for i in range(h):
		for j in range(w):
			if grid[i][j]:
				ok = 1
			else:
				all_A = 0
	if not ok:
		print('MORTAL')
		continue
	if all_A:
		print(0)
		continue
	all_True = 1
	for i in range(w):
		if not grid[0][i]:
			all_True = 0
			break
	if all_True:
		print(1)
		continue
	all_True = 1
	for i in range(w):
		if not grid[-1][i]:
			all_True = 0
			break
	if all_True:
		print(1)
		continue
	all_True = 1
	for i in range(h):
		if not grid[i][0]:
			all_True = 0
			break
	if all_True:
		print(1)
		continue
	all_True = 1
	for i in range(h):
		if not grid[i][-1]:
			all_True = 0
			break
	if all_True:
		print(1)
		continue
	if grid[0][0] | grid[0][-1] | grid[-1][0] | grid[-1][-1]:
		print(2)
		continue
	flg = 0
	for i in range(1, h - 1):
		if sum(grid[i]) == w:
			flg = 1
			break
	for i in range(1, w - 1):
		ok = 1
		for k in range(h):
			if not grid[k][i]:
				ok = 0
				break
		if ok:
			flg = 1
			break
	if flg:
		print(2)
		continue
	any_True = 0
	for i in range(w):
		if grid[0][i]:
			any_True = 1
			break
		if grid[-1][i]:
			any_True = 1
			break
	for i in range(h):
		if grid[i][0]:
			any_True = 1
			break
		if grid[i][-1]:
			any_True = 1
			break
	if any_True:
		print(3)
		continue
	print(4)


import sys
input = sys.stdin.readline

def getInt():
	return int(input())

def getVars():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getStr():
	return input().strip()
t = getInt()
for _ in range(t):
	(rows, columns) = getVars()
	allA = True
	firstARow = False
	firstAColumn1 = True
	firstAColumn2 = True
	inCorner = False
	rowA = False
	oneInFirst = False
	one = False
	d = [1] * max(columns - 2, 0)
	for r in range(rows):
		s = getStr()
		if allA and s != 'A' * len(s):
			allA = False
		if (r == 0 or r == rows - 1) and s == 'A' * len(s):
			firstARow = True
		if firstAColumn1 and s[0] != 'A':
			firstAColumn1 = False
		if firstAColumn2 and s[-1] != 'A':
			firstAColumn2 = False
		if (r == 0 or r == rows - 1) and (s[0] == 'A' or s[-1] == 'A'):
			inCorner = True
		if not rowA and s == 'A' * len(s):
			rowA = True
		for j in range(columns - 2):
			if d[j] == 1 and s[j + 1] == 'P':
				d[j] = 0
		if (r == 0 or r == rows - 1) and s != 'P' * len(s):
			oneInFirst = True
		if not oneInFirst and (s[0] == 'A' or s[-1] == 'A'):
			oneInFirst = True
		if not one and s != 'P' * len(s):
			one = True
	if allA:
		print(0)
	elif firstARow or firstAColumn1 or firstAColumn2:
		print(1)
	elif inCorner or rowA or (len(d) > 0 and max(d) == 1):
		print(2)
	elif oneInFirst:
		print(3)
	elif one:
		print(4)
	else:
		print('MORTAL')


from sys import stdin

def check(lst, c):
	ans = True
	for i in range(len(lst)):
		if lst[i][c] == 'P':
			ans = False
			break
	return ans

def check1(lst, c):
	ans = False
	for i in range(len(lst)):
		if lst[i][c] == 'A':
			ans = True
			break
	return ans

def check2(lst, r):
	ans = False
	for i in range(len(lst[0])):
		if lst[r][i] == 'A':
			ans = True
			break
	return ans

def check3(lst):
	ans = False
	for i in range(len(lst)):
		if lst[i] == ['A'] * len(lst[0]):
			ans = True
			break
	return ans

def check4(lst):
	for i in range(len(lst[0])):
		ans = True
		for j in range(len(lst)):
			if lst[j][i] == 'P':
				ans = False
				break
		if ans:
			break
	return ans
for i in range(int(stdin.readline())):
	(r, c) = map(int, stdin.readline().split())
	lst = []
	god = 0
	for j in range(r):
		lst.append(list(stdin.readline().strip()))
		if lst[-1] == ['A'] * c:
			god += 1
	if god == r:
		print(0)
		continue
	mortality = True
	for j in range(r):
		for k in range(c):
			if lst[j][k] == 'A':
				mortality = False
				break
		if not mortality:
			break
	if mortality:
		print('MORTAL')
	elif lst[0] == ['A'] * c or lst[r - 1] == ['A'] * c:
		print(1)
	elif check(lst, 0) or check(lst, c - 1):
		print(1)
	elif lst[0][0] == 'A' or lst[r - 1][0] == 'A' or lst[0][c - 1] == 'A' or (lst[r - 1][c - 1] == 'A'):
		print(2)
	elif check3(lst) or check4(lst):
		print(2)
	elif check1(lst, 0) or check1(lst, c - 1) or check2(lst, 0) or check2(lst, r - 1):
		print(3)
	else:
		print(4)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	grid = []
	for i in range(r):
		l = list(map(str, input().strip()))
		l2 = [1 if j == 'A' else 0 for j in l]
		grid += [l2]
	summ = 0
	for i in grid:
		summ += sum(i)
	if summ == 0:
		print('MORTAL')
	elif summ == r * c:
		print(0)
	else:
		co = 0
		last = 0
		ex = 0
		for i in range(len(grid)):
			if grid[i][0] != 1:
				last = 1
			else:
				ex += 1
		if last == 1:
			last = 0
			for i in range(len(grid)):
				if grid[i][-1] != 1:
					last = 1
				else:
					ex += 1
		if last == 1:
			last = 0
			for i in range(len(grid[0])):
				if grid[0][i] != 1:
					last = 1
				else:
					ex += 1
		if last == 1:
			last = 0
			for i in range(len(grid[0])):
				if grid[-1][i] != 1:
					last = 1
				else:
					ex += 1
		if last == 0:
			print(1)
		else:
			flag = 0
			if grid[0][0] == 1 or grid[-1][0] == 1 or grid[0][-1] == 1 or (grid[-1][-1] == 1):
				co = 1
			for i in grid:
				if sum(i) == c:
					flag = 1
					break
			for i in range(c):
				s = 0
				for j in range(r):
					s += grid[j][i]
				if s == r:
					flag = 1
					break
			if co == 1:
				if len(grid) == 1 or len(grid[0]) == 1:
					print(1)
				else:
					print(2)
			elif flag == 1:
				print(2)
			elif co != 1 and ex > 0:
				if len(grid) == 1 or len(grid[0]) == 1:
					print(2)
				else:
					print(3)
			else:
				print(4)


import os
import sys
from io import BytesIO, IOBase

def main():
	for t in range(int(input())):
		(n, m) = [int(j) for j in input().split()]
		l = []
		ct_p = 0
		ct_a = 0
		for i in range(n):
			l.append(list(input()))
			ct_a += l[i].count('A')
			ct_p += l[i].count('P')
		if ct_p == 0:
			print(0)
			continue
		elif ct_a == 0:
			print('MORTAL')
			continue
		elif l[0].count('A') == m or l[n - 1].count('A') == m:
			print(1)
			continue
		flag = False
		for i in [0, m - 1]:
			s = 0
			for j in range(n):
				if l[j][i] == 'A':
					s += 1
			if s == n:
				print(1)
				flag = True
				break
		if flag:
			continue
		for i in range(1, n - 1):
			if l[i].count('A') == m:
				print(2)
				flag = True
				break
		if flag:
			continue
		for i in range(1, m - 1):
			s = 0
			for j in range(n):
				if l[j][i] == 'A':
					s += 1
			if s == n:
				print(2)
				flag = True
				break
		if flag:
			continue
		if l[0][m - 1] == 'A' or l[0][0] == 'A' or l[n - 1][m - 1] == 'A' or (l[n - 1][0] == 'A'):
			print(2)
			continue
		for i in [0, n - 1]:
			if flag:
				break
			for j in range(m):
				if l[i][j] == 'A':
					print(3)
					flag = True
					break
		if flag:
			continue
		for i in [0, m - 1]:
			if flag:
				break
			for j in range(n):
				if l[j][i] == 'A':
					print(3)
					flag = True
					break
		if flag:
			continue
		print(4)
		continue
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin
for case in range(int(stdin.readline())):
	(r, c) = [int(x) for x in stdin.readline().split()]
	grid = []
	for x in range(r):
		grid.append(stdin.readline().strip())
	mortal = True
	for x in grid:
		if 'A' in x:
			mortal = False
	if mortal:
		print('MORTAL')
	else:
		grid2 = [''.join([grid[y][x] for y in range(r)]) for x in range(c)]
		allA = True
		for x in grid:
			if 'P' in x:
				allA = False
		if allA:
			print(0)
		elif grid[0] == 'A' * c or grid[-1] == 'A' * c:
			print(1)
		elif grid2[0] == 'A' * r or grid2[-1] == 'A' * r:
			print(1)
		elif grid[0][0] == 'A' or grid[0][-1] == 'A' or grid[-1][-1] == 'A' or (grid[-1][0] == 'A'):
			print(2)
		elif 'A' * c in grid:
			print(2)
		elif 'A' * r in grid2:
			print(2)
		elif 'A' in grid[0] or 'A' in grid[-1]:
			print(3)
		elif 'A' in grid2[0] or 'A' in grid2[-1]:
			print(3)
		else:
			print(4)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(r, c) = list(map(int, input().split()))
	s = [list(input()) for i in range(r)]
	cnt_a = 0
	flag_kado = False
	flag_hen = False
	flag_hen2 = False
	if s[0][0] == 'A' or s[0][c - 1] == 'A' or s[r - 1][0] == 'A' or (s[r - 1][c - 1] == 'A'):
		flag_kado = True
	for i in range(r):
		tmp = 0
		for j in range(c):
			if s[i][j] == 'A':
				if i == 0 or j == 0 or i == r - 1 or (j == c - 1):
					flag_hen2 = True
				tmp += 1
		cnt_a += tmp
		if tmp == c and (i == 0 or i == r - 1):
			flag_hen = True
		elif tmp == c:
			flag_kado = True
	for i in range(c):
		tmp = 0
		for j in range(r):
			if s[j][i] == 'A':
				tmp += 1
		if tmp == r and (i == 0 or i == c - 1):
			flag_hen = True
		elif tmp == r:
			flag_kado = True
	if cnt_a == c * r:
		print(0)
	elif flag_hen:
		print(1)
	elif flag_kado:
		print(2)
	elif flag_hen2:
		print(3)
	elif cnt_a != 0:
		print(4)
	else:
		print('MORTAL')


from sys import stdin, stdout
t = int(stdin.readline())
for i in range(t):
	a = aaa = aa = 0
	(r, c) = map(int, stdin.readline().split())
	x = [0 for _ in range(c)]
	y = [0 for _ in range(r)]
	for j in range(r):
		b = stdin.readline()
		if (j == 0 or j == r - 1) and (b[0] == 'A' or b[c - 1] == 'A'):
			a = 1
		for k in range(c):
			if b[k] == 'A':
				x[k] += 1
				y[j] += 1
				aa += 1
	if aa == c * r:
		stdout.write('0\n')
		continue
	if x[0] == r or x[c - 1] == r or y[0] == c or (y[r - 1] == c):
		stdout.write('1\n')
		continue
	if a >= 1:
		stdout.write('2\n')
		continue
	for jj in range(c):
		if x[jj] == r:
			aaa = 1
	for jj in range(r):
		if y[jj] == c:
			aaa = 1
	if aaa == 1:
		stdout.write('2\n')
		continue
	if x[0] >= 1 or x[c - 1] >= 1 or y[0] >= 1 or (y[r - 1] >= 1):
		stdout.write('3\n')
		continue
	if aa >= 1:
		stdout.write('4\n')
		continue
	if aa == 0:
		stdout.write('MORTAL\n')
		continue


def solve(rows, columns, data):
	(count_A, count_P) = (0, 0)
	count_A_by_row = [0] * rows
	count_A_by_column = [0] * columns
	corner_A = external_A = False
	for (row_number, row) in enumerate(data):
		for (column_number, value) in enumerate(row):
			if value == 'A':
				count_A += 1
				count_A_by_row[row_number] += 1
				count_A_by_column[column_number] += 1
				external_row = row_number == 0 or row_number == rows - 1
				external_column = column_number == 0 or column_number == columns - 1
				if external_row or external_column:
					external_A = True
				if external_row and external_column:
					corner_A = True
	if count_A == 0:
		return 'MORTAL'
	elif count_A == rows * columns:
		return 0
	elif max(count_A_by_row[0], count_A_by_row[-1]) == columns:
		return 1
	elif max(count_A_by_column[0], count_A_by_column[-1]) == rows:
		return 1
	elif corner_A:
		return 2
	elif max(count_A_by_row) == columns:
		return 2
	elif max(count_A_by_column) == rows:
		return 2
	elif external_A:
		return 3
	else:
		return 4
for T in range(int(input())):
	(r, c) = map(int, input().split())
	print(solve(r, c, [input() for _ in range(r)]))


import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def checkr(s, r, c, i):
	for j in range(c):
		if s[i][j] == 'P':
			return False
	return True

def checkc(s, r, c, i):
	for j in range(r):
		if s[j][i] == 'P':
			return False
	return True

def check(s, r, c):
	for i in range(r):
		if s[i][0] == 'A':
			return True
		if s[i][-1] == 'A':
			return True
	for i in range(c):
		if s[0][i] == 'A':
			return True
		if s[-1][i] == 'A':
			return True
	return False
for ik in range(int(input())):
	(r, c) = map(int, input().split())
	s = []
	e = 0
	e1 = 0
	for i in range(r):
		s.append(input())
		e += s[-1].count('A')
		e1 += s[-1].count('P')
	if e == 0:
		print('MORTAL')
		continue
	if e1 == 0:
		print(0)
		continue
	if checkc(s, r, c, 0) or checkc(s, r, c, c - 1) or checkr(s, r, c, 0) or checkr(s, r, c, r - 1):
		print(1)
	else:
		f = 0
		for i in range(1, c - 1):
			if checkc(s, r, c, i):
				f = 1
				break
		for i in range(1, r - 1):
			if checkr(s, r, c, i):
				f = 1
				break
		if f == 1:
			print(2)
		elif s[0][0] == 'A' or s[0][-1] == 'A' or s[-1][-1] == 'A' or (s[-1][0] == 'A'):
			print(2)
		elif check(s, r, c):
			print(3)
		else:
			print(4)


from sys import stdin, stdout
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	mp = []
	one = False
	every = True
	for _ in range(a):
		mp.append([])
		for x in stdin.readline().strip():
			if x == 'A':
				mp[-1].append(1)
				one = True
			else:
				mp[-1].append(0)
				every = False
	if every == True:
		print(0)
		continue
	if one == False:
		print('MORTAL')
		continue
	line = []
	for i in (0, -1):
		line.append(mp[i])
		line.append([])
		for j in range(a):
			line[-1].append(mp[j][i])
	t = []
	s = []
	for x in line:
		t.append(all(x))
		s.append(any(x))
	if any(t):
		print(1)
		continue
	u = []
	for i in (0, -1):
		for j in (0, -1):
			u.append(mp[i][j])
	for x in mp:
		u.append(all(x))
	for i in range(b):
		u.append(all([mp[j][i] for j in range(a)]))
	if any(u):
		print(2)
	elif any(s):
		print(3)
	else:
		print(4)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for j in range(t):
	(r, c) = map(int, input().split())
	grid = []
	for s in range(r):
		vals = [k for k in input()]
		grid.append(vals)
	ans = [0 for s in range(5)]
	A = 0
	P = 0
	for s in range(r):
		row = 0
		for i in range(c):
			if grid[s][i] == 'A':
				A += 1
				row += 1
				if (s == 0 or s == r - 1) and (i == 0 or i == c - 1):
					ans[2] += 1
				elif s == 0 or s == r - 1 or i == 0 or (i == c - 1):
					ans[3] += 1
				else:
					ans[4] += 1
			else:
				P += 1
		if row == c:
			if s == 0 or s == r - 1:
				ans[1] += 1
			else:
				ans[2] += 1
	if A == 0:
		print('MORTAL')
	elif P == 0:
		print(0)
	else:
		for i in range(c):
			col = 0
			for s in range(r):
				if grid[s][i] == 'A':
					col += 1
			if col == r:
				if i == 0 or i == c - 1:
					ans[1] += 1
				else:
					ans[2] += 1
		for s in range(len(ans)):
			if ans[s] > 0:
				print(s)
				break


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a += [[k for k in input()]]
	pos = False
	has = False
	for i in range(n):
		for j in range(m):
			if a[i][j] == 'A':
				pos = True
			else:
				has = True
	if not pos:
		print('MORTAL')
		continue
	if not has:
		print(0)
		continue
	first_row = a[0]
	last_row = a[-1]
	first_col = [a[k][0] for k in range(n)]
	last_col = [a[k][-1] for k in range(n)]
	if first_row == ['A'] * m or last_row == ['A'] * m or first_col == ['A'] * n or (last_col == ['A'] * n):
		print(1)
		continue
	pos = False
	for i in a:
		if i == ['A'] * m:
			pos = True
			break
	for j in range(m):
		if [a[i][j] for i in range(n)] == ['A'] * n:
			pos = True
			break
	if 'A' in [a[0][0], a[0][-1], a[-1][0], a[-1][-1]] or min(n, m) == 1 or pos:
		print(2)
		continue
	if 'A' in first_row + first_col + last_col + last_row:
		print(3)
		continue
	print(4)


from sys import stdin, stdout
t = int(stdin.readline())
for k in range(t):
	rc = list(map(int, stdin.readline().split()))
	r = rc[0]
	c = rc[1]
	b = False
	allA = True
	corner = False
	border = False
	allR = False
	allR_border = False
	allC = False
	allC_border = False
	prestr = ''
	allca = [True] * c
	for i in range(r):
		rstr = stdin.readline()
		allr = True
		for j in range(c):
			v = rstr[j]
			if v == 'A':
				b = True
				if j > 0 and v != rstr[j]:
					allr = False
				if i > 0 and v != prestr[j]:
					allca[j] = False
				if i == 0 or j == 0 or i == r - 1 or (j == c - 1):
					border = True
				if i == 0 and j == 0 or (i == 0 and j == c - 1) or (i == r - 1 and j == 0) or (i == r - 1 and j == c - 1):
					corner = True
			else:
				allr = False
				allca[j] = False
				allA = False
		prestr = rstr
		allR |= allr
		if allr and (i == 0 or i == r - 1):
			allR_border = True
	for i in range(len(allca)):
		allC |= allca[i]
		if allca[i] and (i == 0 or i == len(allca) - 1):
			allC_border = True
	res = 'MORTAL'
	if b:
		if allA:
			res = '0'
		elif allC_border or allR_border:
			res = '1'
		elif allR or allC:
			res = '2'
		elif corner:
			res = '2'
		elif border:
			res = '3'
		else:
			res = '4'
	stdout.write(res + '\n')


import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input())

def li2():
	return [i for i in input().rstrip('\n').split(' ')]
for _ in range(val()):
	(n, m) = li()
	l = []
	for i in range(n):
		l.append(st())
	l1 = [set() for i in range(n)]
	l2 = [set() for i in range(m)]
	ans = -1
	ans2 = -1
	for i in range(n):
		for j in l[i]:
			if j == 'A':
				ans = 4
			else:
				ans2 = 1
	if ans == -1:
		print('MORTAL')
		continue
	if ans2 == -1:
		print(0)
		continue
	for i in range(n):
		for j in range(m):
			if l[i][j] == 'A':
				l1[i].add(j)
				l2[j].add(i)
	ans = 4
	if len(l1[0]) == m or len(l1[-1]) == m or len(l2[0]) == n or (len(l2[-1]) == n):
		print(1)
		continue
	if 0 in l1[0] or 0 in l1[-1] or 0 in l2[0] or (0 in l2[-1]) or (m - 1 in l1[0]) or (m - 1 in l1[-1]) or (n - 1 in l2[0]) or (n - 1 in l2[-1]):
		print(2)
		continue
	for i in range(n):
		if len(l1[i]) == m:
			ans = 2
			break
	for j in range(m):
		if len(l2[j]) == n:
			ans = 2
			break
	if ans == 2:
		print(2)
		continue
	for i in range(n):
		if 0 in l1[i] or m - 1 in l1[i]:
			ans = 3
			break
	for j in range(m):
		if 0 in l2[j] or n - 1 in l2[j]:
			ans = 3
			break
	print(ans)


INF = 10 ** 10

def main():
	print = out.append
	(r, c) = get_list()
	mat = [list(input()) for _ in range(r)]
	all_A = True
	for li in mat:
		if 'P' in li:
			all_A = False
	if all_A:
		print(0)
		return
	res = chk_Mat(mat)
	new_mat = []
	for i in range(c):
		li = []
		for j in range(r):
			li.append(mat[j][i])
		new_mat.append(li)
	res = min(res, chk_Mat(new_mat))
	print(res) if res <= 4 else print('MORTAL')

def chk_Mat(mat):
	(r, c) = (len(mat), len(mat[0]))

	def row_cst(row):
		if 'P' not in mat[row]:
			return 0
		if mat[row][0] == 'A' or mat[row][-1] == 'A':
			return 1
		return 2 if 'A' in mat[row] else INF
	res = min(row_cst(0) + 1, row_cst(-1) + 1)
	for j in range(1, r - 1):
		res = min(res, row_cst(j) + 2)
	return res
import sys
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
[main() for _ in range(int(input()))]
print(*out, sep='\n')


import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())

def solve():
	(r, c) = map(int, input().split())
	s = []
	cnt = 0
	for _ in range(r):
		tmp = input()
		cnt += tmp.count('A')
		s.append(tmp)
	if cnt == 0:
		print('MORTAL')
		return
	if cnt == r * c:
		print(0)
		return
	for i in range(r):
		if s[i][0] == 'P':
			break
	else:
		print(1)
		return
	for i in range(r):
		if s[i][-1] == 'P':
			break
	else:
		print(1)
		return
	for i in range(c):
		if s[0][i] == 'P':
			break
	else:
		print(1)
		return
	for i in range(c):
		if s[-1][i] == 'P':
			break
	else:
		print(1)
		return
	if s[0][0] == 'A' or s[0][-1] == 'A' or s[-1][0] == 'A' or (s[-1][-1] == 'A'):
		print(2)
		return
	for i in range(r):
		if s[i][0] == 'P':
			b = i
			break
	for i in range(r - 1, -1, -1):
		if s[i][0] == 'P':
			e = i + 1
			break
	for i in range(1, c):
		for j in range(b, e):
			if s[j][i] == 'P':
				break
		else:
			print(2)
			return
	for i in range(r):
		if s[i][-1] == 'P':
			b = i
			break
	for i in range(r - 1, -1, -1):
		if s[i][-1] == 'P':
			e = i + 1
			break
	for i in range(c - 1):
		for j in range(b, e):
			if s[j][i] == 'P':
				break
		else:
			print(2)
			return
	for i in range(c):
		if s[0][i] == 'P':
			b = i
			break
	for i in range(c - 1, -1, -1):
		if s[0][i] == 'P':
			e = i + 1
			break
	for i in range(1, r):
		for j in range(b, e):
			if s[i][j] == 'P':
				break
		else:
			print(2)
			return
	for i in range(c):
		if s[-1][i] == 'P':
			b = i
			break
	for i in range(c - 1, -1, -1):
		if s[-1][i] == 'P':
			e = i + 1
			break
	for i in range(r - 1):
		for j in range(b, e):
			if s[i][j] == 'P':
				break
		else:
			print(2)
			return
	for i in range(r):
		if s[i][0] == 'A' or s[i][-1] == 'A':
			print(3)
			return
	for i in range(c):
		if s[0][i] == 'A' or s[-1][i] == 'A':
			print(3)
			return
	print(4)
for _ in range(t):
	solve()


import sys

def all(l):
	for i in range(len(l)):
		if l[i] != 'A':
			return False
	return True

def all_col(grid, j):
	for i in range(r):
		if grid[i][j] != 'A':
			return False
	return True

def get(grid):
	ans = float('inf')
	(r, c) = (len(grid), len(grid[0]))
	for i in range(r):
		(left, right) = (-1, -1)
		if all(grid[i]):
			if i == 0 or i == r - 1:
				return 1
			else:
				ans = min(ans, 2)
		for j in range(c):
			if grid[i][j] == 'A':
				left = j
				break
		if left == -1:
			continue
		for j in range(c - 1, -1, -1):
			if grid[i][j] == 'A':
				right = j
				break
		if left == 0 or left == c - 1:
			if i == 0 or i == r - 1:
				ans = min(ans, 2)
			else:
				ans = min(ans, 3)
		elif i == 0 or i == r - 1:
			ans = min(ans, 3)
		else:
			ans = min(ans, 4)
		if right == 0 or right == c - 1:
			if i == 0 or i == r - 1:
				ans = min(ans, 2)
			else:
				ans = min(ans, 3)
		elif i == 0 or i == r - 1:
			ans = min(ans, 3)
		else:
			ans = min(ans, 4)
	for i in range(c):
		if all_col(grid, i):
			if i == 0 or i == c - 1:
				return 1
			else:
				ans = min(ans, 2)
		(top, down) = (-1, -1)
		for j in range(r):
			if grid[j][i] == 'A':
				top = j
				break
		if top == -1:
			continue
		for j in range(r - 1, -1, -1):
			if grid[j][i] == 'A':
				down = j
				break
		if top == 0:
			if i == 0 or i == c - 1:
				ans = min(ans, 2)
			else:
				ans = min(ans, 3)
		elif i == 0 or i == c - 1:
			ans = min(ans, 3)
		else:
			ans = min(ans, 4)
		if down == r - 1:
			if i == 0 or i == c - 1:
				ans = min(ans, 2)
			else:
				ans = min(ans, 3)
		elif i == 0 or i == c - 1:
			ans = min(ans, 3)
		else:
			ans = min(ans, 4)
	if ans == float('inf'):
		return -1
	return ans

def check_all(grid):
	(r, c) = (len(grid), len(grid[0]))
	for i in range(r):
		for j in range(c):
			if grid[i][j] != 'A':
				return False
	return True
t = int(sys.stdin.readline())
for _ in range(t):
	(r, c) = map(int, sys.stdin.readline().split())
	l = []
	for i in range(r):
		s = sys.stdin.readline()[:-1]
		l.append(s)
	if check_all(l):
		print(0)
	else:
		x = get(l)
		if x == -1:
			print('MORTAL')
		else:
			print(x)


def ifp(s):
	flag = 1
	for i in mat:
		if s in i:
			flag = 0
			break
	if flag:
		return False
	return True

def check3():
	if 'A' in mat[0] or 'A' in mat[-1]:
		return True
	flag1 = 0
	flag2 = 0
	for i in range(r):
		if mat[i][0] == 'A':
			flag1 = 1
		if mat[i][-1] == 'A':
			flag2 = 1
	if flag1 or flag2:
		return True
	return False
for nt in range(int(input())):
	(r, c) = map(int, input().split())
	mat = []
	for i in range(r):
		mat.append(input())
	if not ifp('A'):
		print('MORTAL')
		continue
	if not ifp('P'):
		print(0)
		continue
	if 'P' not in mat[0] or 'P' not in mat[-1]:
		print(1)
		continue
	flag1 = 0
	flag2 = 0
	for i in range(r):
		if 'P' == mat[i][0]:
			flag1 = 1
		if 'P' == mat[i][-1]:
			flag2 = 1
	if not flag1 or not flag2:
		print(1)
		continue
	if mat[0][0] == 'A' or mat[0][-1] == 'A' or mat[-1][0] == 'A' or (mat[-1][-1] == 'A'):
		print(2)
		continue
	flag = 0
	for i in range(r):
		if 'P' not in mat[i]:
			flag = 1
			break
	for i in range(c):
		flag2 = 0
		for j in range(r):
			if mat[j][i] == 'P':
				flag2 = 1
				break
		if not flag2:
			flag = 1
			break
	if flag:
		print(2)
		continue
	if check3():
		print(3)
		continue
	print(4)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from collections import defaultdict as dd
(t,) = I()
while t:
	t -= 1
	(n, m) = I()
	g = []
	c = [[] for i in range(m)]
	p = False
	a = False
	for i in range(n):
		g.append(input())
		s = g[-1]
		for j in range(m):
			if s[j] == 'A':
				a = True
			else:
				p = True
			c[j].append(s[j])
	if not p:
		print(0)
		continue
	if not a:
		print('MORTAL')
		continue
	ans = 4
	for i in range(n):
		if 'P' not in g[i]:
			if i == 0 or i == n - 1:
				ans = 1
				break
			else:
				ans = min(ans, 2)
	for i in range(m):
		if 'P' not in c[i]:
			if i == 0 or i == m - 1:
				ans = 1
				break
			else:
				ans = min(ans, 2)
	if 'A' in [g[0][0], g[0][-1], g[-1][0], g[-1][-1]]:
		ans = min(ans, 2)
	for i in range(m):
		if g[0][i] == 'A' or g[-1][i] == 'A':
			ans = min(ans, 3)
			break
	for i in range(n):
		if g[i][0] == 'A' or g[i][-1] == 'A':
			ans = min(ans, 3)
	print(ans)


import sys
input = sys.stdin.readline
Q = int(input())
Query = []
for _ in range(Q):
	(H, W) = map(int, input().split())
	state = [list(input().rstrip()) for _ in range(H)]
	Query.append((H, W, state))

def main(H, W, state):
	ok = False
	for h in range(H):
		for w in range(W):
			if state[h][w] == 'A':
				ok = True
				break
		if ok:
			break
	if not ok:
		return 'MORTAL'
	ok = False
	for h in range(H):
		for w in range(W):
			if state[h][w] == 'P':
				ok = True
				break
		if ok:
			break
	if not ok:
		return 0
	ok = False
	for h in range(H):
		if state[h][0] == 'P':
			ok = True
			break
	if not ok:
		return 1
	ok = False
	for h in range(H):
		if state[h][-1] == 'P':
			ok = True
			break
	if not ok:
		return 1
	ok = False
	for w in range(W):
		if state[0][w] == 'P':
			ok = True
			break
	if not ok:
		return 1
	ok = False
	for w in range(W):
		if state[-1][w] == 'P':
			ok = True
			break
	if not ok:
		return 1
	for h in range(H):
		ok = False
		for w in range(W):
			if state[h][w] == 'P':
				ok = True
				break
		if not ok:
			return 2
	for w in range(W):
		ok = False
		for h in range(H):
			if state[h][w] == 'P':
				ok = True
				break
		if not ok:
			return 2
	if state[0][0] == 'A' or state[0][-1] == 'A' or state[-1][0] == 'A' or (state[-1][-1] == 'A'):
		return 2
	for h in range(H):
		if state[h][0] == 'A' or state[h][-1] == 'A':
			return 3
	for w in range(W):
		if state[0][w] == 'A' or state[-1][w] == 'A':
			return 3
	return 4
for (H, W, state) in Query:
	ans = main(H, W, state)
	print(ans)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def solve():
	(r, c) = map(int, input().split())
	board = [[int(j == 'A') for j in input()] for i in range(r)]
	board2 = [list(x) for x in zip(*board)]
	s = sum((sum(board[i]) for i in range(r)))
	if s == 0:
		print('MORTAL')
		return
	elif s == r * c:
		print(0)
		return
	else:
		if any((sum(board[i]) == c for i in [0, r - 1])) or any((sum(board2[i]) == r for i in [0, c - 1])):
			print(1)
			return
		if board[0][0] + board[0][-1] + board[-1][0] + board[-1][-1] > 0:
			print(2)
			return
		if any((sum(board[i]) == c for i in range(r))) or any((sum(board2[i]) == r for i in range(c))):
			print(2)
			return
		if any((sum(board[i]) > 0 for i in [0, r - 1])) or any((sum(board2[i]) > 0 for i in [0, c - 1])):
			print(3)
			return
		print(4)
		return
t = int(input())
for i in range(t):
	solve()


import math, collections, sys
input = sys.stdin.readline

def calc(r, c):
	rows = [0 for i in range(r)]
	cols = [0 for i in range(c)]
	total = 0
	for i in range(r):
		for j in range(c):
			if z[i][j] == 'A':
				rows[i] += 1
				cols[j] += 1
				total += 1
	if total == r * c:
		return 0
	if total == 0:
		return 'MORTAL'
	if rows[0] == c or rows[-1] == c or cols[0] == r or (cols[-1] == r):
		return 1
	if z[0][0] == 'A' or z[0][-1] == 'A' or z[-1][0] == 'A' or (z[-1][-1] == 'A'):
		return 2
	if max(rows) == c or max(cols) == r:
		return 2
	if rows[0] or rows[-1] or cols[0] or cols[-1]:
		return 3
	return 4
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	z = []
	for i in range(r):
		z.append(input().strip())
	print(calc(r, c))


import sys
input = lambda : sys.stdin.readline().rstrip()
for i in ' ' * int(input()):
	(a, b) = map(int, input().split())
	L = []
	M = [[] for j in range(b)]
	A = False
	P = False
	for j in ' ' * a:
		s = input()
		if 'A' in s:
			A = True
		if 'P' in s:
			P = True
		for k in range(b):
			M[k].append(s[k])
		L.append(s)
	for j in range(len(M)):
		M[j] = ''.join(M[j])
	if not A:
		print('MORTAL')
		continue
	if not P:
		print(0)
		continue
	ss = L[0] + L[-1] + M[0] + M[-1]
	if 'P' not in L[0] or 'P' not in L[-1] or 'P' not in M[0] or ('P' not in M[-1]):
		print(1)
		continue
	if L[0][0] == 'A' or L[0][-1] == 'A' or L[-1][0] == 'A' or (L[-1][-1] == 'A'):
		print(2)
		continue
	A2 = False
	for j in L:
		if 'P' not in j:
			A2 = True
	for j in M:
		if 'P' not in j:
			A2 = True
	if A2:
		print(2)
		continue
	if 'A' in ss:
		print(3)
	else:
		print(4)


from sys import stdin
for case in range(int(stdin.readline())):
	(n, m) = [int(x) for x in stdin.readline().split()]
	r = [0 for _ in range(n)]
	c = [0 for _ in range(m)]
	has = 0
	total = 0
	mxR = 0
	mxC = 0
	for it in range(n):
		a = stdin.readline().strip()
		if (it == 0 or it == n - 1) and (a[0] == 'A' or a[m - 1] == 'A'):
			has = 1
		for i in range(m):
			if a[i] == 'A':
				total += 1
				r[it] += 1
				c[i] += 1
				mxR = max(mxR, r[it])
				mxC = max(mxC, c[i])
	if total == 0:
		print('MORTAL')
		continue
	if total == n * m:
		print(0)
		continue
	if r[0] == m or r[n - 1] == m or c[0] == n or (c[m - 1] == n):
		print(1)
		continue
	if has > 0:
		print(2)
		continue
	if mxR == m or mxC == n:
		print(2)
		continue
	if r[0] + r[n - 1] + c[0] + c[m - 1] > 0:
		print(3)
		continue
	else:
		print(4)


from sys import stdin, stdout

def f(a, r):
	for i in range(r):
		if 'A' in a[i]:
			return False
	return True

def ff(a, r):
	for i in range(r):
		if 'P' in a[i]:
			return False
	return True
for __ in range(int(stdin.readline())):
	(r, c) = map(int, stdin.readline().split())
	a = []
	for i in range(r):
		inpu = stdin.readline()
		a.append(inpu)
	if f(a, r):
		stdout.write('MORTAL' + '\n')
	elif ff(a, r):
		stdout.write('0' + '\n')
	else:
		browalla = False
		bcolalla = False
		if 'P' not in a[0] or 'P' not in a[r - 1]:
			browalla = True
		t1 = True
		t2 = True
		for i in range(r):
			if a[i][0] == 'P':
				t1 = False
			if a[i][c - 1] == 'P':
				t2 = False
		bcolalla = t1 or t2
		if browalla or bcolalla:
			stdout.write('1' + '\n')
		else:
			rownoa = False
			colrowa = True
			if 'A' not in a[0] and 'A' not in a[r - 1]:
				rownoa = True
			for i in range(r):
				if a[i][0] == 'A' or a[i][c - 1] == 'A':
					colrowa = False
			if rownoa and colrowa:
				stdout.write('4' + '\n')
			else:
				rowalla = False
				colalla = False
				for i in range(r):
					if 'P' not in a[i]:
						rowalla = True
				for i in range(c):
					col = True
					for j in range(r):
						if a[j][i] == 'P':
							col = False
					if col:
						colalla = col
				if rowalla or colalla or (a[0][0] == 'A' or a[0][c - 1] == 'A' or a[r - 1][0] == 'A' or (a[r - 1][c - 1] == 'A')):
					stdout.write('2' + '\n')
				else:
					stdout.write('3' + '\n')
	stdin.flush()
	stdout.flush()


import sys
for _ in range(int(input())):
	(r, c) = list(map(int, input().split()))
	a = [[] for _ in range(r)]
	row_count = [0] * r
	a_total = 0
	for y in range(r):
		a[y] = [1 if c == 'A' else 0 for c in sys.stdin.readline().rstrip()]
		row_count[y] = sum(a[y])
		a_total += row_count[y]
	if a_total == r * c:
		print(0)
		continue
	if a_total == 0:
		print('MORTAL')
		continue
	col_count = [0] * c
	for x in range(c):
		for y in range(r):
			col_count[x] += a[y][x]
	if row_count[0] == c or row_count[-1] == c or col_count[0] == r or (col_count[-1] == r):
		print(1)
		continue
	if a[0][0] | a[0][-1] | a[-1][0] | a[-1][-1] == 1:
		print(2)
		continue
	if any((rcnt == c for rcnt in row_count)) or any((ccnt == r for ccnt in col_count)):
		print(2)
		continue
	if row_count[0] or row_count[-1] or col_count[0] or col_count[-1]:
		print(3)
		continue
	print(4)


from sys import stdin, stdout
T = int(stdin.readline())
out = []
for _ in range(T):
	(r, c) = map(int, stdin.readline().split())
	rows = [stdin.readline() for _ in range(r)]
	columns = []
	for i in range(c):
		columns.append(''.join((row[i] for row in rows)))
	b = True
	for row in rows:
		if 'P' in row:
			b = False
			break
	if b:
		out.append('0\n')
		continue
	if 'P' not in rows[0] or 'P' not in rows[r - 1] or 'P' not in columns[0] or ('P' not in columns[c - 1]):
		out.append('1\n')
		continue
	if rows[0][0] == 'A' or rows[r - 1][0] == 'A' or rows[0][c - 1] == 'A' or (rows[r - 1][c - 1] == 'A'):
		out.append('2\n')
		continue
	else:
		b = False
		for i in range(1, r - 1):
			if 'P' not in rows[i]:
				b = True
				break
		if b:
			out.append('2\n')
			continue
		for i in range(1, c - 1):
			if 'P' not in columns[i]:
				b = True
				break
		if b:
			out.append('2\n')
			continue
	if 'A' in rows[0] or 'A' in rows[r - 1] or 'A' in columns[0] or ('A' in columns[c - 1]):
		out.append('3\n')
		continue
	b = False
	for row in rows:
		if 'A' in row:
			b = True
			break
	if b:
		out.append('4\n')
	else:
		out.append('MORTAL\n')
stdout.writelines(out)


from sys import stdin
rstr = lambda : stdin.readline().strip()
rstr_2d = lambda n: [rstr() for _ in range(n)]
rints = lambda : [int(x) for x in stdin.readline().split()]
out = []
for _ in range(int(input())):
	(n, m) = rints()
	(mat, row, col, su) = (rstr_2d(n), [0] * n, [0] * m, 0)
	for i in range(n):
		for j in range(m):
			if mat[i][j] == 'A':
				row[i] += 1
				col[j] += 1
				su += 1
	if not su:
		out.append('MORTAL')
	elif su == n * m:
		out.append('0')
	elif m in [row[0], row[-1]] or n in [col[0], col[-1]]:
		out.append('1')
	elif 'A' in [mat[0][0], mat[0][-1], mat[-1][0], mat[-1][-1]] or max(row) == m or max(col) == n:
		out.append('2')
	elif any([row[0], row[-1], col[0], col[-1]]):
		out.append('3')
	else:
		out.append('4')
print('\n'.join(out))


import sys
import bisect
import heapq
from math import *
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
mod = pow(10, 9) + 7

def inp():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nl():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def solve():
	(n, m) = sep()
	a = []
	f0 = True
	imp = True
	for i in range(0, n):
		temp = list(inp())
		if temp.count('A') < m:
			f0 = False
		if temp.count('A') > 0:
			imp = False
		a.append(temp)
	if imp:
		print('MORTAL')
	elif f0:
		print(0)
	else:
		col = []
		for j in range(0, m):
			temp = []
			for i in range(0, n):
				temp.append(a[i][j])
			col.append(temp)
		if a[0].count('A') == m or a[n - 1].count('A') == m or col[m - 1].count('A') == n or (col[0].count('A') == n):
			print(1)
		else:
			f1 = False
			f2 = False
			f3 = False
			cnt = 0
			for i in range(0, n):
				cnt = max(cnt, a[i].count('A'))
			if cnt == m:
				f1 = True
			cnt = 0
			for i in range(0, m):
				cnt = max(cnt, col[i].count('A'))
			if cnt == n:
				f2 = True
			if a[0][0] == 'A' or a[0][m - 1] == 'A' or a[n - 1][0] == 'A' or (a[n - 1][m - 1] == 'A'):
				f3 = True
			if f1 or f2 or f3:
				print(2)
			elif a[0].count('A') > 0 or a[n - 1].count('A') > 0 or col[0].count('A') > 0 or (col[m - 1].count('A') > 0):
				print(3)
			else:
				print(4)
testcase(int(inp()))


import sys

def solve(g, r, c):
	total = sum((sum(row) for row in g))
	if total == r * c:
		return 0
	if total == 0:
		return 'MORTAL'
	if all(g[0]) or all(g[-1]):
		return 1
	if all((g[i][0] for i in range(r))) or all((g[i][-1] for i in range(r))):
		return 1
	if any([g[0][0], g[0][-1], g[-1][0], g[-1][-1]]):
		return 2
	for row in g:
		if all(row):
			return 2
	for i in range(c):
		if all((g[j][i] for j in range(r))):
			return 2
	if any(g[0]) or any(g[-1]):
		return 3
	if any((g[i][0] for i in range(r))) or any((g[i][-1] for i in range(r))):
		return 3
	return 4
lines = list(sys.stdin.readlines())
t = int(lines[0])
i = 1
for _ in range(t):
	(r, c) = map(int, lines[i].split())
	i += 1
	g = []
	for _ in range(r):
		row = list([c == 'A' for c in lines[i][:c]])
		i += 1
		g.append(row)
	print(solve(g, r, c))


import sys
reader = (line.rstrip() for line in sys.stdin)
n = int(next(reader))
for _ in range(n):
	(r, c) = [int(x) for x in next(reader).split()]
	turns = float('inf')
	cols = [[] for j in range(c)]
	onlyA = True
	onlyP = True
	for i in range(r):
		row = [el == 'A' for el in next(reader)]
		if onlyA:
			onlyA = all(row)
		if onlyP:
			onlyP = not any(row)
		if all(row):
			if 0 < i < r - 1:
				turns = min(turns, 2)
			else:
				turns = min(turns, 1)
		elif row[0] or row[-1]:
			if 0 < i < r - 1:
				turns = min(turns, 3)
			else:
				turns = min(turns, 2)
		elif any(row):
			if 0 < i < r - 1:
				turns = min(turns, 4)
			else:
				turns = min(turns, 3)
		for (j, el) in enumerate(row):
			cols[j].append(el)
	for i in range(c):
		col = cols[i]
		if all(col):
			if 0 < i < c - 1:
				turns = min(turns, 2)
			else:
				turns = min(turns, 1)
	if onlyA:
		print(0)
	elif onlyP:
		print('MORTAL')
	else:
		print(turns)


import sys
input = sys.stdin.readline
import heapq
import copy
import math

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

class Node:

	def _init_(self, val):
		self.data = val
		self.left = None
		self.right = None

class fen_tree:

	def __init__(self, list):
		self.array = [0] + list
		for idx in range(1, len(self.array)):
			idx2 = idx + (idx & -idx)
			if idx2 < len(self.array):
				self.array[idx2] += self.array[idx]

	def prefix_query(self, idx):
		result = 0
		while idx:
			result += self.array[idx]
			idx -= idx & -idx
		return result

	def prints(self):
		print(self.array)
		return

	def range_query(self, from_idx, to_idx):
		return self.prefix_query(to_idx) - self.prefix_query(from_idx - 1)

	def update(self, idx, add):
		while idx < len(self.array):
			self.array[idx] += add
			idx += idx & -idx

def pre_sum(arr):
	p = [0]
	for i in arr:
		p.append(p[-1] + i)
	p.pop(0)
	return p

def pre_back(arr):
	p = [0]
	for i in arr:
		p.append(p[-1] + i)
	p.pop(0)
	return p

def bin_search(arr, l, r, val):
	if arr[r] <= val:
		return r + 1
	if r - l < 2:
		if arr[l] > val:
			return l
		else:
			return r
	mid = int((l + r) / 2)
	if arr[mid] <= val:
		return bin_search(arr, mid, r, val)
	else:
		return bin_search(arr, l, mid, val)

def search_leftmost(arr, val):

	def helper(arr, l, r, val):
		print(l, r)
		if arr[l] == val:
			return l
		if r - l <= 1:
			if arr[r] == val:
				return r
			else:
				print('not found')
				return
		mid = int((r + l) / 2)
		if arr[mid] >= val:
			return helper(arr, l, mid, val)
		else:
			return helper(arr, mid, r, val)
	return helper(arr, 0, len(arr) - 1, val)

def search_rightmost(arr, val):

	def helper(arr, l, r, val):
		print(l, r)
		if arr[r] == val:
			return r
		if r - l <= 1:
			if arr[l] == val:
				return r
			else:
				print('not found')
				return
		mid = int((r + l) / 2)
		if arr[mid] > val:
			return helper(arr, l, mid, val)
		else:
			return helper(arr, mid, r, val)
	return helper(arr, 0, len(arr) - 1, val)

def pr_list(a):
	print(*a, sep=' ')

def main():
	tests = inp()
	mod = 1000000007
	limit = 10 ** 18
	for test in range(tests):
		[r, c] = inlt()
		grid = []
		for i in range(r):
			grid.append(insr())
		rows = [0 for i in range(r)]
		col = [0 for i in range(c)]
		for i in range(r):
			for j in range(c):
				if grid[i][j] == 'A':
					rows[i] += 1
					col[j] += 1
		if max(rows) == 0:
			print('MORTAL')
		elif sum(rows) == r * c:
			print(0)
		elif rows[0] == c or col[0] == r or rows[-1] == c or (col[-1] == r):
			print(1)
		elif grid[0][0] == 'A' or grid[-1][0] == 'A' or grid[0][-1] == 'A' or (grid[-1][-1] == 'A') or (max(rows) == c) or (max(col) == r):
			print(2)
		elif rows[0] != 0 or col[0] != 0 or col[-1] != 0 or (rows[-1] != 0):
			print(3)
		else:
			print(4)
main()


import sys
import math
from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	cnt = 0
	l = []
	flag = 0
	flag2 = 0
	h = [0, 0]
	v = [0, 0]
	for i in range(r):
		s = list(input())
		cur = 1
		for j in range(c):
			if s[j] == 'A':
				s[j] = 1
				cnt += 1
				if j == 0 or j == c - 1:
					flag = 1
					if j == 0:
						v[0] += 1
					else:
						v[1] += 1
				if i == 0 or i == r - 1:
					flag = 1
					if i == 0:
						h[0] += 1
					else:
						h[1] += 1
			else:
				s[j] = 0
				cur = 0
		if cur:
			flag2 = 1
		l.append(s)
	if cnt == 0:
		print('MORTAL')
	elif cnt == r * c:
		print(0)
	elif flag == 0:
		print(4)
	else:
		if max(h) == c or max(v) == r:
			print(1)
			flag = 0
		if flag:
			if l[0][0] or l[0][c - 1] or l[r - 1][c - 1] or l[r - 1][0] or flag2:
				print(2)
			else:
				for j in range(1, c - 1):
					for k in range(r):
						if l[k][j] == 0:
							break
					else:
						print(2)
						flag2 = 1
						break
				if flag2 == 0:
					print(3)


def solve():
	(r, c) = [int(x) for x in input().split()]
	matrix = []
	for rows in range(r):
		delta = list(input())
		matrix.append(delta)
	c1 = 0
	corner = 0
	for i in range(r):
		if matrix[i][0] == 'A':
			corner = 1
		if matrix[i][0] != 'A':
			c1 = 1
	cl = 0
	for i in range(r):
		if matrix[i][c - 1] == 'A':
			corner = 1
		if matrix[i][c - 1] != 'A':
			cl = 1
	r1 = 0
	for j in range(c):
		if matrix[0][j] == 'A':
			corner = 1
		if matrix[0][j] != 'A':
			r1 = 1
	rl = 0
	for j in range(c):
		if matrix[r - 1][j] == 'A':
			corner = 1
		if matrix[r - 1][j] != 'A':
			rl = 1
	aA = 0
	aP = 0
	for i in range(r):
		for j in range(c):
			if matrix[i][j] == 'A':
				aP = 1
			if matrix[i][j] == 'P':
				aA = 1
	if aA == 0:
		print('0')
		return
	if aP == 0:
		print('MORTAL')
		return
	if r1 == 0 or rl == 0 or c1 == 0 or (cl == 0):
		print(1)
		return
	if matrix[0][0] == 'A' or matrix[r - 1][0] == 'A' or matrix[0][c - 1] == 'A' or (matrix[r - 1][c - 1] == 'A'):
		print(2)
		return
	for i in range(r):
		flag = 0
		for j in range(c):
			if matrix[i][j] == 'P':
				flag = 1
				break
		if flag == 0:
			print(2)
			return
	for j in range(c):
		flag = 0
		for i in range(r):
			if matrix[i][j] == 'P':
				flag = 1
				break
		if flag == 0:
			print(2)
			return
	if corner == 1:
		print(3)
		return
	print(4)
	return
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
t = int(input())
for test in range(t):
	solve()


def main():
	allans = []
	t = int(input())
	for _ in range(t):
		(n, m) = readIntArr()
		arr = []
		for __ in range(n):
			arr.append(input())
		aCnts = 0
		for i in range(n):
			for j in range(m):
				if arr[i][j] == 'A':
					aCnts += 1
		if aCnts == n * m:
			allans.append(0)
		elif aCnts == 0:
			allans.append('MORTAL')
		else:
			rowFullyFilled = [True for __ in range(n)]
			for i in range(n):
				for j in range(m):
					if arr[i][j] != 'A':
						rowFullyFilled[i] = False
						break
			colfullyFilled = [True for __ in range(m)]
			for j in range(m):
				for i in range(n):
					if arr[i][j] != 'A':
						colfullyFilled[j] = False
						break
			if rowFullyFilled[0] or rowFullyFilled[-1] or colfullyFilled[0] or colfullyFilled[-1]:
				allans.append(1)
			elif True in rowFullyFilled or True in colfullyFilled:
				allans.append(2)
			elif arr[0][0] == 'A' or arr[0][-1] == 'A' or arr[-1][0] == 'A' or (arr[-1][-1] == 'A'):
				allans.append(2)
			else:
				aOnEdge = False
				for i in range(n):
					if arr[i][0] == 'A' or arr[i][-1] == 'A':
						aOnEdge = True
						break
				for j in range(m):
					if arr[0][j] == 'A' or arr[-1][j] == 'A':
						aOnEdge = True
						break
				if aOnEdge:
					allans.append(3)
				else:
					allans.append(4)
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]
inf = float('inf')
MOD = 10 ** 9 + 7
main()