You are given a N×M grid.
Each point in the grid can contain one of the four symbols described below:
|Symbol|Description|
|---|
|''|Your current position in the grid|
|'x'* |A special position in the grid|
|'.' |This position can be used for travelling|
|'#' |This position cannot be used for travelling|
Distance of one point is equal from all 8 of its surrounding points.
You have to find the distance of the nearest and farthest special positions from your current position in the grid.
Input format:
First line contains T, denoting the number of test cases. T test cases follow.
First line of each test case contains space separated values of N and M.
Next N lines contain M characters each. The character can be either of four characters described above.
Output format:
T lines each containing space separated values of the shortest distance and the longest distance.
If there is no path from current position to any of the special positions, print -1
Input constraints:
1≤T≤200
3≤N,M≤200
Case #1:
Current position: (3,1)
Nearest ' * ' is at (3,2) which is at distance 1.
Farthest ' * ' is at (1,2) which is at distance 3. (3,1) -> (3,2) -> (2,3) -> (1,2)
Case #3:
Current position: (4,4)
Nearest ' * ' is at (3,3) which is at distance 1. (4,4) -> (3,3)
Farthest ' * ' is at (1,1) which is at distance 3. (4,4) -> (3,3) -> (2,2) -> (1,1)
