In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 21st
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #10 exercise sheet]

[AED060] 2D Maze

Imagine you are implementing a game with a maze represented by a matrix. The player's objective () is to reach the treasure () in as few moves as possible, and can move horizontally or vertically to neighbouring cells. A possible maze is shown below (left figure) and the number of moves it takes the player to reach each cell from their starting position (right figure).

The maze is represented by a character matrix, where '#' represents a wall, '.' an empty cell, 'P' the player and 'T' the treasure. For example, the maze above would be represented by:

The Problem

Given a character maze of R rows by C columns as described above, your task is to compute the minimum moves that the player need to make to reach the treasure.

Input

The first line of the input contains a number N indicating the number of cases to consider.

Each of the cases begins with two numbers R and C indicating respectively the number of rows and columns of the maze to be considered, followed by R lines, each with C characters, indicating the content of each position: '.' for an empty position, '#' for a wall, 'P' for the player and 'T' for the treasure.

You can assume that the maze will contain exactly one position with a player and exactly one position with a treasure. You can also assume that there exists a path between the player and the treasure and that there will always exist walls separating the inside of the maze from the outside.

Output

The output should consist of N lines, one for each input case. Each one should have a single integer indicating the number of moves the player needs to make to reach the treasure.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

2
9 10
##########
#..P.....#
#.##.###.#
#..#.....#
##.#.#.###
#....#...#
#.######.#
#.....T..#
##########
5 5
#####
#..P#
#.#.#
#T..#
#####

13
4

Explanation of Example Input

The first case corresponds to the figure in the problem statement, in which the player needs to make 13 moves.

In the second case the player needs to make 4 moves: down→down→left→left.