406752: GYM102535 I Knight's Tour: The Beginnings

I. Knight's Tour: The Beginningstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Properly sneaking into a mission is very important for spies, which is lucky for you, because the Cavalry Valet Movile Insertion Group (CVMIG) has given one of their horses to you. The problem is, you are not a knight yet! In order for the horse to follow your commands, it must deem you worthy of being a knight!

Fortunately, proving yourself worthy of knightliness is easy. All horses are part of the chess club, and love how knights move. You just need to show them that you can get to your destination just like how a knight would.

In chess, a knight moves in an L shaped pattern, moving 1 space to its side then 2 spaces forward, landing on that final square. It can hop over obstacles.

Consider the following diagram:

The knight, shown at the center, may move around in $$$8$$$ ways relative to the knight's current position, labeled 'A', 'B', ..., 'H'. The knight may do that even if the squares immediately surrounding it are obstacles.

You will be given an $$$R \times C$$$ grid of characters. Each character is one of the following:

• O means that you may land on this spot.
• X means that you cannot land on this spot.
• K is the spot you start on. There is exactly one K in the grid.
• F is the spot you must end on. There is exactly one F in the grid.

Find out if it is possible to move from your initial spot to the final spot while moving like a knight in a chess game.

Output "Whinny" if it's possible and "Neigh" if it is not. If it is possible, also output a string denoting the moves the knight can follow to the final spot.

Note that the knight cannot leave the grid. In other words, it is not allowed to perform a move if the desination cell is outside the grid.

Input

The first line of the input contains a single integer $$$t$$$, the number of test cases. $$$t$$$ test cases follow.

The first line of each test case contains two integers $$$r$$$ and $$$c$$$. $$$r$$$ lines follow, each containing $$$c$$$ characters, describing the grid using the abovementioned denotations.

Constraints

$$$1 \leq t \leq 10$$$

$$$1 \leq r,c \leq 1000$$$

Output

For each test case, output a single line containing "Whinny" if it's possible to reach F from K using knight moves, "Neigh" otherwise.

If it's possible, output an additional line containing a string denoting the series of moves the knight can follow. The string should be composed of characters 'A', 'B', ..., 'H' indicating the type of move done. If there are multiple such move-strings available, output the shortest one. If there are multiple shortest move-strings, output the lexicographically-least move-string.

ExampleInput

3
2 3
OOF
KOO
2 3
OOO
KOF
4 6
OFKOOO
OOXXOO
OOXOOO
OXOOOX

Output

Whinny
D
Neigh
Whinny
FAFAC