It's down to the final match in the world's biggest SC2$^1$ tournament! You're the MVP$^2$ of MVP$^3$, and you're going up against MVP$^4$. There are $G$ ($1 \leq G \leq 20$) games in the series, with a winner decided after all have been played. Being a Protoss$^5$ player, you know the perfect way to win against that Terran$^6$ scum - with a cannon rush$^7$ every single game. Now you just have to execute it perfectly, by quickly getting your probe$^{10}$ to the correct location, and the prize money's sure to be yours.

Each game will take place on a map which can be represented as a grid with $H$ ($2 \leq H \leq 1000$) rows of $W$ ($2 \leq W \leq 1000$) cells each. Each cell contains either empty space (represented by "E"), water ("W"), a unit ("U"), one of exactly two mineral patches ("M"), the probe ("P"), or the cannon rush site ("C"). Every second, your probe can move to a horizontally- or vertically-adjacent cell within the grid, with the goal of reaching the cannon rush site in as little time as possible. It can move freely from an empty cell to another empty cell (including its initial position and destination), while cells containing water or minerals may never be traversed.

Normally, the probe may also not pass through units. However, it can if it is travelling towards a mineral patch. Specifically, the probe can only leave or enter a cell containing a unit if, for at least one of the two mineral patches on the map, the cell which the probe is entering is closer to that patch than the cell which the probe is leaving. Closeness is defined according to the minimum amount of time it would take to reach the mineral patch from the given cell, assuming the ability to pass through all units on the way.

For each game, you'd like to determine whether or not you can be successful in your strategy, and, if so, how quickly you can execute the cannon rush. Of course, the point of this is to help prepare the correct BM$^{11}$ for the end of the game.

Input

First line: 1 integer, $G$

For each game:

First line: 2 integers, $H$ and $W$

Next $H$ lines: $W$ characters, representing the $i$th row of the map, for $i = 1..H$

Output

For each game:

The BM to be typed at the conclusion of the game. Namely, if the probe can reach the cannon rush site, the string "pwned you in $X$ seconds eZ$^{12}$, learn to play n00b$^{13}$" (without the quotes and glossary numbers), where $X$ is the minimum number of seconds for it to do so - otherwise, the string "terran so broken, apologize for playing this race".

Example

Input:
2
4 5
WWEMC
EEEUE
PUWWU
MEEEE
5 4
EWEM
ECUE
EEWE
EWEE
EUPM

Output:
pwned you in 8 seconds eZ, learn to play n00b
terran so broken, apologize for playing this race

Explanation of Sample:

In the first scenario, the single shortest path that the probe may take to the cannon rush site is illustrated below:

Note that the first move is made by going "towards" the top-right mineral patch, while the second move is made by going towards the bottom-left one.

In the second scenario, the probe is unable to pass through any of the units, due to the locations of the mineral patches, and as such cannot reach its destination.

Glossary of Terms:

$^1$ SC2: StarCraft 2, by Blizzard Entertainment - a game of kings

$^2$ MVP: Most valuable player

$^3$ MVP: A top Korean SC2 team

$^4$ MVP: A top Korean Terran player (who is not on the team MVP)

$^5$ Protoss: The most pleasant race in SC2, which only nice people use

$^6$ Terran: The most despicable race in SC2, which no decent human being would consider 

$^7$ Cannon rush: The act of building proxy$^8$ cannons, a common type of cheese$^9$

$^8$ Proxy: A structure made near or in your opponent's base, instead of your own

$^9$ Cheese: A perfectly legitimate strategy which can allow you to win quickly, while leaving your opponent mad

$^{10}$ Probe: A Protoss unit most useful for its ability to make cannons

$^{11}$ BM: Customary parting words for your opponent, used to convey your respect for them

$^{12}$ eZ: Easy

$^{13}$ n00b: A player whose skill is somewhat lacking in calibre