You may have played the game 'Blade and Sword', it's an action game. However, in this problem we are actually solving one stage of the game.

For simplicity, assume that the game stage can be modeled as a 2D grid which has m rows and n columns. The cells are categorized as follows:

• . represents an empty space. The player can move through it.
• # represents wall, and the player cannot move through it. You can assume that the boundaries of the grid will be walls.
• * means a teleporting cell, once the player moves into this cell, he must choose any other teleporting cell where he will be taken to. But if he cannot find a desired teleporting cell, he will die. However, after moving to the desired teleporting cell, he can either move to an adjacent cell, or he can teleport again using the same procedure.
• P means the position of the player and there will be exactly one cell containing P.
• D means the destination cell and there will be exactly one cell containing D.

Now you are given a stage and the player starts moving. It takes one unit of time for the player to move to any adjacent cell from his current position. Two cells are adjacent if they share a side. One unit of time is needed for the teleporting service; that means taking the player from one teleporting cell to any other teleporting cell. Your task is to find the minimum possible time unit required for the player to reach the destination cell.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing two integers: m and n (3 ≤ m, n ≤ 200). Each of the next m lines contains n characters denoting the stage. The given stage follows the restrictions stated above.

For each case, print the case number and the minimum required time. If it's impossible for the player to reach the destination cell, print impossible. See the samples for details.