Original problem statement (in Polish) can be found here.

Dorian the Caretaker hates mowing the lawn. There is nothing worse than listening to this monotonous purr of the engine and inhaling its fumes for a few hours solid. Unfortunately, it just so happens that cutting the grass on the local millionaire's golf course is his only duty.

But, fortunately for Dorian, salvation is here! His employer bought the newest miracle of engineering - Super Mower 3000, which can be remotely controlled. No more monotony, no more sweat and toil! Dorian will be finally fired, so he can start something he wanted to start for a long time - the search for a new job. No proper education and lack of prospects will only make it more fun.

Super Mower 3000 has to be programmed beforehand, though. The golf course is a rectangle with n rows and m columns, which consists of square-shaped fields 1 meter wide. Some fields contain just grass, other fields have obstacles on them. Super Mower can instantly cut the grass just by being on the field. It cannot enter the field with an obstacle. Every grass-covered field is reachable from every other grass-covered field.

Initially, Super Mower stands on the field in the first column of the first row, facing right. It executes a sequence of commands afterwards. There are four different commands:

• N - move one field forwards
• W - move one field backwards
• L - rotate 90 degrees left
• P - rotate 90 degrees right

Moving one field forwards or backwards takes one second. Rotations are slower and take three seconds each.

Given a description of the golf course, devise the sequence of commands that will make Super Mower mow the whole lawn (that is, it will visit every grass-covered field), while taking the least amount of time.

Input

The first line contains a single integer t, denoting the number of testcases. (t <= 10). The descriptions of the testcases follow.

First line of the description consists of two integers n and m (2 <= n,m <= 100), denoting the size of the golf course. Then n lines follow, each containg m characters. The j-th character in the i-th line describes the field in the i-th row and j-th column. "." (a dot) indicates a grass covered field, "#" indicates an obstacle. It is guaranteed that the first field is grass-covered.

Output

For each test case print one line with a string containing only letters "N", "L", "W" or "P", denoting the sequence of commands for Super Mower 3000 to execute. The sequence should make Super Mower visit every grass-covered field, without entering a field with an obstacle or going outside the course, and it cannot be longer than 16*n*m commands.

Example

Input:

2
4 7
.......
.##.##.
.##.##.
.......
4 8
........
...#.###
.#.#....
.#.#....

Output:

NNNNNNPNNNPNNNPNNWWLNNNPNN
NNNNNNNWWWPNNNLNNNLNLNNNPNNLNNLNNNWWPNNLNN

Scoring

If the sequence of commands satisfies all the conditions given in the problem statement, and it takes x seconds to execute, it is worth x/(n*m) points. Overall score is equal to the sum of individual scores.

Sample test explanation

The first sequence takes 36 seconds to execute, the second sequence takes 60 seconds. Then, your score is 36/(4*7) + 60/(4*8), so about 3.16.