Afshung Pizza Delivery

The Afshung-Pizza chain runs a door-to-door pizza delivery service in Hamedung, a district of Sildavya, and it needs your help to plan the fastest possible delivery. Every rider carries a GIS device that shows all of Hamedung's streets and computes a route to the customer. The Elyasung Company, which builds and maintains the device, wants you to reprogram it so that it returns an even faster route.

Hamedung is a rectangular district whose two-way streets are all rectilinear (axis-aligned). The device draws the map with text characters, using the legend below:

• Each - (dash) is one kilometer of west-east street, and each | (pipe) is one kilometer of north-south street.
• A + marks a sharp 90-degree turn of zero length that has no traffic light.
• A single digit $\tau$ (from 1 to 9) marks an intersection whose traffic light has timing $\tau$. Every intersection is either three-way or four-way.
• S marks an Afshung-Pizza branch (the start) and D marks the delivery address (the destination).
• * characters mark the border of the district.

To keep the district safe and free of accidents, every traffic light shows exactly one green and the rest red (two red lights at a three-way intersection, three at a four-way). One direction stays green for $\tau$ minutes — that is, during $[x, x + \tau)$ for some $x$ — and during the next $\tau$ minutes the green moves to the next direction, rotating counterclockwise. The same rule holds at every intersection.

Time is zero at the moment the rider starts moving. At time zero every intersection is set so that only its southern light is green — or, if the intersection has no southern street, its northern light — while all of its other lights are red.

The rider can change direction only at a turn (+) or at an intersection (a digit). For example, in a pattern such as -|-, a rider moving horizontally can neither cross the pipe nor turn, because there is no intersection there.

Given the map, the branch S, and the destination D, write a program that finds the fastest route to deliver the pizza from S to D. Assume the following:

• S and D each replace a - or a |.
• S and D are not adjacent to any intersection or turn.
• S and D are not adjacent to each other.
• Any two intersections and/or turns are at least one kilometer apart.
• S, D, +, and every digit have zero length.
• The rider travels at one kilometer per minute.
• A rider facing a green light may move in any direction (straight, left, or right); no movement is allowed while facing a red light.
• There are no traffic jams or other obstacles along the way.

The first line contains an integer $t$ ($1 \le t \le 10$), the number of test cases.

Each test case begins with a line containing two integers $N$ ($1 \le N \le 100$), the number of map rows, and $M$ ($2 \le M \le 100$), the number of map columns. The next $N$ lines each contain a string of length $M$ made up of the characters -, |, +, (space), *, S, D, and the digits 1-9. The total number of intersections and turns (+) is at most 100.

For each test case, print one line containing the minimum number of minutes needed to drive from S to D, or the word impossible (in lowercase letters) if D cannot be reached.