지나치게 들뜬 팬

오늘이 바로 그날이다. 드디어 고양이 Peppurr와 사진을 찍을 날이 왔다!

Peppurr가 당신의 도시를 순회한다는 소식이 방금 발표되었다. 이 도시에는 남북 방향으로 뻗은 무한히 긴 길이 무한히 많고, 동서 방향으로 뻗은 무한히 긴 길도 무한히 많다. 교차점은 남북 방향 길과 동서 방향 길이 만나는 지점이다. 어느 교차점에서든 북, 동, 남, 서 네 방향에서 가장 가까운 교차점은 정확히 1블록 떨어져 있다.

Peppurr의 순회 경로가 이 길들을 따라 어떻게 이어지는지 정확히 알고 있다. 목표는 Peppurr가 순회 경로의 교차점에 있을 때 같은 시각에 같은 교차점에 있는 것이다. 가능한 한 빨리 그렇게 하고 싶다. 이것이 Peppurr와 사진을 찍는 방법이다!

Peppurr의 순회는 당신이 지금 있는 교차점에서 동쪽으로 X블록, 북쪽으로 Y블록 떨어진 교차점에서 시작한다. 당신과 Peppurr는 모두 한 블록을 걷는 데 정확히 1분이 걸리며, 매 분이 끝날 때 반드시 교차점에 있어야 한다. 둘 중 누구도 블록의 일부만 걸을 수 없다.

Peppurr는 미리 정해진 경로를 따라 움직인다. 매 분마다 당신은 그 자리에 서 있을 수도 있고, 그 1분 동안 북, 동, 남, 서 네 방향 중 한 방향으로 한 블록을 걸을 수도 있다. 당신과 Peppurr 모두 길 위로만 걷는다.

당신과 Peppurr가 같은 시각에 같은 교차점에 있으면 사진을 찍을 수 있다. 순회의 마지막 교차점에서도 가능하다. 다만 Peppurr는 순회가 끝난 뒤에는 사진에 응하지 않는다. 따라서 순회가 끝나고 단 1분이라도 늦게 마지막 교차점에 도착하면 사진을 찍을 수 없다.

Peppurr와 사진을 찍는 것이 가능한가? 가능하다면 가장 빨리 언제 찍을 수 있는가?

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 나온다. 각 케이스는 정수 X와 Y가 적힌 한 줄과 문자열 M으로 이루어진다. 이는 Peppurr의 순회가 당신보다 정확히 동쪽으로 X블록, 북쪽으로 Y블록 떨어진 곳에서 시작한다는 뜻이다. 문자열 M은 Peppurr가 움직일 순서이다. M의 i번째 문자는 N, E, S, W 중 하나이며, 순회의 i번째 분에 Peppurr가 각각 북, 동, 남, 서 방향으로 한 블록을 걷는다는 뜻이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이다. Peppurr와 사진을 찍을 방법이 없다면 y는 IMPOSSIBLE이다. 그렇지 않다면 y는 순회가 시작된 뒤 사진을 찍기까지 필요한 최소 분 수이다.

• $1 \le T \le 100$.
• $(X, Y) \ne (0, 0)$. 순회는 당신이 있는 교차점에서 시작하지 않는다.

샘플 케이스 #1에서는 동쪽으로 4블록 걸으면, 순회의 마지막 교차점에서 Peppurr와 사진을 찍을 수 있다.

샘플 케이스 #2에서는 순회가 당신보다 정확히 동쪽으로 3블록 떨어진 곳에서 시작한다. 어떻게 움직이든 Peppurr와 사진을 찍을 수 없다.

샘플 케이스 #3에서는 순회가 너무 북쪽에 있어서, 순회가 끝나기 전에 사진을 찍을 수 없다.

샘플 케이스 #4에서는 순회가 1분 뒤 당신에게 오므로, 움직일 필요도 없다. Peppurr와의 사진을 즐기자! 사진은 교차점에서만 찍을 수 있다는 점에 유의하라. 당신이 북쪽으로 움직이고 순회가 남쪽으로 움직여서 교차점 밖에서 Peppurr와 엇갈리게 된다면, 0.5분 안에는 사진을 찍을 수 없다.

샘플 케이스 #5에서는 북쪽으로 두 번 움직인 뒤 동쪽으로 두 번 움직일 수 있다. 그다음 제자리에 머물면, 다음 1분에 Peppurr와 사진을 찍을 수 있다. 5분 만에 사진을 찍는 다른 경로도 있지만, 그보다 빨리 찍는 경로는 없다.

다음 두 케이스는 테스트 세트 1이나 2에는 나올 수 없지만, 테스트 세트 3에는 나올 수 있다.

2
3 2 SSSW
4 0 NESW

이 두 케이스의 올바른 출력은 다음과 같다.

Case #1: 4
Case #2: 4

케이스 #1에서 당신은 처음 출발점에서 남쪽으로 1블록, 동쪽으로 2블록 떨어진 곳에서 Peppurr와 사진을 찍을 수 있다.

케이스 #2에서 Peppurr는 작은 정사각형을 돈다. Peppurr가 그 정사각형의 출발점으로 돌아오면 사진을 찍을 수 있다.