CF374C.Inna and Dima

Inna and Dima bought a table of size n × m in the shop. Each cell of the table contains a single letter: "D", "I", "M", "A".

Inna loves Dima, so she wants to go through his name as many times as possible as she moves through the table. For that, Inna acts as follows:

1. initially, Inna chooses some cell of the table where letter "D" is written;
2. then Inna can move to some side-adjacent table cell that contains letter "I"; then from this cell she can go to one of the side-adjacent table cells that contains the written letter "M"; then she can go to a side-adjacent cell that contains letter "A". Then Inna assumes that she has gone through her sweetheart's name;
3. Inna's next move can be going to one of the side-adjacent table cells that contains letter "D" and then walk on through name DIMA in the similar manner. Inna never skips a letter. So, from the letter "D" she always goes to the letter "I", from the letter "I" she always goes the to letter "M", from the letter "M" she always goes to the letter "A", and from the letter "A" she always goes to the letter "D".

Depending on the choice of the initial table cell, Inna can go through name DIMA either an infinite number of times or some positive finite number of times or she can't go through his name once. Help Inna find out what maximum number of times she can go through name DIMA.

因娜和迪马在商店买了一张大小为 $n \times m$ 的表格。表格的每个格子中恰好包含一个字母：“D”、“I”、“M” 或 “A”。

因娜深爱着迪马，因此她希望在遍历表格的过程中，尽可能多地完整走过他的名字 “DIMA”。为此，因娜按如下方式行动：

1. 最初，因娜选择表格中某个写有字母 “D” 的格子作为起点；
2. 接着，因娜可以移动到一个与当前格子边相邻（即上下左右四个方向之一）且含有字母 “I” 的格子；然后从该格子再移动到一个边相邻且含有字母 “M” 的格子；再接着移动到一个边相邻且含有字母 “A” 的格子。此时，因娜认为她已完整走过一次爱人的名字；
3. 因娜的下一步可以是移动到一个边相邻且含有字母 “D” 的格子，然后以类似方式继续遍历名字 “DIMA”。因娜绝不会跳过任何一个字母。也就是说，从字母 “D” 出发时，她总是必须前往字母 “I”；从字母 “I” 出发时，她总是必须前往字母 “M”；从字母 “M” 出发时，她总是必须前往字母 “A”；而从字母 “A” 出发时，她总是必须前往字母 “D”。

根据初始所选格子的不同，因娜可能能够无限次地遍历名字 “DIMA”，也可能只能遍历某个正的有限次数，甚至一次也无法完成。请帮助因娜找出她最多能完整遍历名字 “DIMA” 多少次。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 103).

Then follow n lines that describe Inna and Dima's table. Each line contains m characters. Each character is one of the following four characters: "D", "I", "M", "A".

Note that it is not guaranteed that the table contains at least one letter "D".

输入的第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 10^3$）。

接下来是 $n$ 行，描述了 Inna 和 Dima 的表格。每行包含 $m$ 个字符。每个字符是以下四个字符之一：“D”、“I”、“M”、“A”。

注意：不能保证表格中至少包含一个字母 “D”。

If Inna cannot go through name DIMA once, print on a single line "Poor Dima!" without the quotes. If there is the infinite number of names DIMA Inna can go through, print "Poor Inna!" without the quotes. Otherwise print a single integer — the maximum number of times Inna can go through name DIMA.

如果茵娜无法完整遍历一次名字“DIMA”，则在一行中输出 "Poor Dima!"（不带引号）。
如果茵娜可以无限次遍历名字“DIMA”，则输出 "Poor Inna!"（不带引号）。
否则，输出一个整数——茵娜最多能遍历名字“DIMA”的次数。

Notes to the samples:

In the first test sample, Inna cannot go through name DIMA a single time.

In the second test sample, Inna can go through the infinite number of words DIMA. For that, she should move in the clockwise direction starting from the lower right corner.

In the third test sample the best strategy is to start from the cell in the upper left corner of the table. Starting from this cell, Inna can go through name DIMA four times.

样例说明：

在第一个测试样例中，Inna 无法完整遍历一次单词 “DIMA”。

在第二个测试样例中，Inna 可以无限次地遍历单词 “DIMA”。为此，她应从右下角开始，沿顺时针方向移动。

在第三个测试样例中，最优策略是从表格左上角的格子出发。从该格子出发，Inna 可以完整遍历单词 “DIMA” 四次。