Anna University Local Contest #8

Save Ryan Stone who lost her target in a space mission. For every unit time, she can move 1 step within the map in one of the 8 possible directions adjacent to her current position (diagonal, vertical or horizontal). Ryan Stone must not hit any objects on her way. She must reach her target before her Oxygen level goes down to 0%. At every unit time, the O2 level goes down by 1%.

Find whether she can reach the target before O2 level goes below 0%.

Input:

The first line consists of an integer t, the number of test cases. For each test case, the first line consists of three integers O, m and n - the level of Oxygen, the number of rows and columns in the 2D space map followed by m strings of length n representing the map.

'S' denotes the starting point of Ryan Stone and 'T' denotes the target point. '#' represents immovable objects and ' ' represents a free space.

Output:

For each test case print "Possible" if she can achieve the target, "Impossible" otherwise.

Input Constraints:

1<=t<=1000

1<=O<=100

2<=m,n<=100

map[i][j] ∈ {' ','S','T','#'}

There will be exactly one Start point(S) and one Target point(T)

Sample Input:

4
1 2 2
#T
S#
1 3 2
#T
  
S#
2 3 2
T#
# 
S#
10 2 4
S #T
  ##

Sample Output:

Possible
Impossible
Possible
Impossible

Note: As there are lot of spaces in the input file, take care of Input.