Woburn Challenge 1999 - Suicidal

So if you'll remember, both Ethan Hunt and Will Hunting are janitors at this college and since their collective genius has been untapped, they are coming up with a game to decide who is smarter. One of them will run through a maze to find the other person in the shortest possible time. If you've ever toured Scarborough Campus, you will appreciate that it can in fact be a maze sometimes.

In addition, it is of note that this is a fairly modern college – so modern in fact is the college that there are teleporters scattered throughout the school. Every teleporter is in ~2~ parts – when you step into ~1~ part, you are teleported into the other part (from here on, "teleporter" refers to both parts in total).

Each teleporter is controlled by a switch located somewhere in the college. When the switch is activated, the teleporter it is associated with is turned on for a specific period of time (i.e. a certain number of moves on your part) after which it is turned off again. A switch is located in the hallway and is turned on when you walk on it. If you step on a switch to a transporter that has already been activated, you reset its time. Every transporter has exactly ~1~ switch controlling it.

The teleporters are part of the walls. When you walk into a teleporter that is activated, you are instantaneously (i.e. at no time cost), transported to your destination which is the other half of the same teleporter. So, your only cost to teleporting is the ~1~ step it takes you to step onto the teleporter – you instantly materialize on the other teleporter. Note that if a teleporter is not activated, it behaves just like a wall and if it is activated and you step into it, you will be transported.

You will start from a location and you will be given the ending location where Ethan will be. You need to get to Ethan in the least amount of time. Note that it may not be possible to get to Ethan, in which case you output IMPOSSIBLE. If it is possible, you output the least number of steps you need to take to reach Ethan. Note that it takes ~1~ step to step into the exit.

Input Specification

Line ~1~: Number of input sets

The ~1~st line of the input sets will consist of ~m\ n~ where ~m~ is the number of rows in the maze and ~n~ is the number of columns ~(m,n \le 100)~.
The ~2~nd line contains the length of time that each teleporter is activated for (all teleporters have the same length of time that they are activated for).

Then, you will be given an ~m \times n~ maze with the following legend. Every block can either be a W,  , X, Y, a to t or A to T.

W = Wall
X = Starting location
Y = Finishing location
  = Empty space to walk in
a-t = Teleporters. Each teleporter is given a unique designation from a to t. Both halves of the teleporter are given the same designation.
A-T = Switches. Switch A controls teleporter a and so on.

Output Specification

For each test case, output the least amount of time in which Ethan can reach the finishing location, and IMPOSSIBLE otherwise.

Sample Input

1
8 10
5
WWWWWWWWWW
W W bW   W
Y a  WX  W
W W  WWAaW
W     b  W
W  WW BWWW
W  W  W  W
WWWWWWWWWW

Sample Output

5