Escape

James B. is a secret service agent, usually assigned to the most dangerous and most spectacular missions. On his latest assignment he must obtain a copy of a set of classified files so that his team gains an edge over its rivals.

Being a superstar agent, James easily entered the building where the files are kept on an offline computer and copied them onto his USB stick. But on his way out he tripped an experimental intrusion-detection system installed by one of the professors, and now the campus security service is chasing him.

The security cars are no match for James' car. As long as he keeps driving and never stands still, they can only follow him and can never catch him. An escape helicopter is scheduled to pick him up in a few minutes. Because the helicopter can wait at the pick-up point for only a limited time, James wants to arrive there just in time: as early as possible once the helicopter has arrived. He cannot wait at the pick-up point (the guards would catch up), so he will jump into the hovering helicopter from the roof of his moving car.

You are given the map of the city, James' start location (the university), the pick-up location, the time the helicopter arrives, and the maximum number of seconds it can wait. Find the earliest time James can be at the pick-up location while the helicopter is still waiting.

James moves at a speed of one block per second and may move north, east, south, or west whenever the target field allows it (see the table). Because the guards follow him closely he cannot make a U-turn, and because he cannot stand still he must always move to an adjacent field, but never back to the field he just came from.

The fields are described by these characters:

The university, where James stands at time $0$, is marked U. The pick-up location, where the helicopter arrives at time $t$, is marked X. On his first move James may go in any direction the adjacent fields allow. He may pass through the pick-up location before the scheduled arrival time if necessary.

The first line contains the number of scenarios.

Each scenario begins with a line containing two integers $R$ and $C$ ($1 \le R, C \le 50$). The next $R$ lines each contain $C$ characters describing the city layout. The scenario ends with a line containing two integers: the number of seconds $t$ until the helicopter arrives and the number of seconds $d$ it can wait for James ($1 \le t, d \le 600$).

For each scenario, first print a line “Scenario #i:”, where $i$ is the scenario number starting at 1. On the next line print the smallest $t'$ with $t \le t' < t + d$ such that James can be at the pick-up location after exactly $t'$ seconds, or “Impossible” if he cannot escape by helicopter. Separate consecutive scenarios with a blank line.