Overexcited Fan

Today will be the day, today will be the day that you finally get a picture with Peppurr the cat!

It has just been announced that Peppurr will be touring your city. The city has infinitely many infinitely-long streets running north-south and infinitely many infinitely-long streets running east-west. An intersection is any point at which a north-south street and an east-west street meet. From any given intersection, the closest intersection in each of the four directions (north, east, south and west) is exactly one block away.

You know the exact path that Peppurr's tour will take along those streets. Your goal is to be at one of the intersections on Peppurr's tour at the same time that Peppurr is there, and you want to do so as fast as possible. This is how you will get your picture with Peppurr!

Peppurr's tour starts at an intersection that is X blocks east and Y blocks north of the intersection where you are currently located. Both you and Peppurr take exactly one minute to walk one full block, and must finish each minute at an intersection. Neither of you can walk partial blocks.

Peppurr moves along a predefined path. Every minute, you can choose to stand still, or use the minute to walk a single block in any of the 4 directions (north, east, south or west). Both you and Peppurr only walk along the streets.

If you and Peppurr are at the same intersection at the same time, you can take a picture, even at the last intersection of the tour. However, Peppurr is unavailable for pictures after the tour ends, so arriving at the tour's final intersection even a single minute after the tour finishes means you will not get a picture.

Is it possible to get a picture with Peppurr? If so, how soon can you do it?

The first line of the input gives the number of test cases, T. T test cases follow. Each case consists of one line containing two integers, X and Y, and a string of characters M. This means that Peppurr's tour starts exactly X blocks east and Y blocks north of you. The string M is the sequence of moves that Peppurr will make. The i-th character in M is one of N, E, S or W, and corresponds to the direction (north, east, south, or west, respectively) in which Peppurr walks one block during the tour's i-th minute.

For each test case, output one line with Case #x: y, where x is the test case number (starting from 1). If there is no way to get a picture with Peppurr, y is IMPOSSIBLE. Otherwise, y is the smallest number of minutes from the start of the tour needed to get a picture with Peppurr.

• $1 \le T \le 100$.
• $(X, Y) \ne (0, 0)$. The tour does not start at the same intersection as you.

In Sample Case #1, you can walk east four blocks, and you will be able to take a picture with Peppurr at the tour's last intersection.

In Sample Case #2, the tour starts exactly three blocks east of you. No matter how you move, you cannot get a picture with Peppurr.

In Sample Case #3, the tour is too far north for you to get the picture before the tour ends.

In Sample Case #4, the tour comes to you after one minute, so you don't even have to move! Enjoy the picture with Peppurr! Remember that you can only take pictures at intersections. If you moved north while the tour moved south, you would cross paths with Peppurr outside of an intersection, and you could not get your picture in 0.5 minutes.

In Sample Case #5, you can move north twice, then east twice. Then you can stay still, and you will be able to take a picture with Peppurr in the next minute. Other paths can get you a picture in 5 minutes, but none can do it sooner.

The following two cases could not appear in Test Set 1 or Test Set 2, but could appear in Test Set 3:

2
3 2 SSSW
4 0 NESW

The correct output for these two cases would be:

Case #1: 4
Case #2: 4

In Case #1, you can take a picture with Peppurr one block south and two blocks east of your original starting point.

In Case #2, Peppurr travels in a small square. You can take a picture when Peppurr returns to the starting point of that square.