A soccer field is divided into squared plots, like a grid of N rows and M columns. The length of a plot side is equal to 1. Fernando likes to practice running only through the boundaries of the plots, he does not like to go inside the plots.

Some of the plots are muddy, and some others have been selected by Fernando as target plots. A plot may neither be muddy nor a target one.

Starting at the top left corner, he would like to go through the field and return back to the starting point. All plots that lie inside the cycle of his path are considered to be inspected. To make things more interesting he would like his path not to intersect with itself in any point different than the starting point. Luckily, the plots boundaries are so wide that Fernando can go along the same boundary multiple times without intersecting his own path.

Fernando would like to inspect all target plots, but not any muddy plots. Martin, who plays in the opposing team, challenged Fernando that he could do a shortest path starting from the lower right corner. Can you help Fernando to get his shortest path, and decide whether it is shorter than the one?

Input

Input consist of many test cases.

First line of input starts with two integers R and C (1 <= R, C <= 50), which defines the rows and columns the soccer field has been divided into.

Next, the soccer field is described in R rows, each containing C characters. Chars I, X, and O, represents target plots (to inspect), muddy plots, and common plots respectively. The quantity of target plots plus the quantity of muddy plots will not exceed 10.

There will be no spaces between the C characters of each line describing the soccer field.

End of the input is indicated by a line containing two zeros, which should not be processed.

Output

The output of each test case should be a separate line consisting of the name of the player who has the shortest path to inspect the target plots but not the muddy plots, or the word “Tie” in case of a tie, followed by a number representing the length of the shortest path for that player. The examples may clarify the format.

Example

Input:
1 1 
I 
2 2 
XX 
XI 
2 2 
XI 
IX 
3 3 
III 
IXI 
III 
2 2 
IO 
OO 
0 0

Output:
Tie 4
Martin 4
Tie 10
Tie 18
Fernando 4