종이 접기 좌표

종이 띠가 하나 있고, 이 띠를 다음 두 가지 방법 중 하나로 반복해서 접는다.

• 위로 접기(U): 띠의 오른쪽 끝을 왼쪽 끝 위로 가져와 반으로 접는다. 넘어간 절반이 위쪽에 놓인다.
• 아래로 접기(L): 띠의 오른쪽 끝을 왼쪽 끝으로 가져와 반으로 접는다. 넘어간 절반이 아래쪽에 놓인다.

여러 번 접은 뒤, 다시 펼치면서 모든 접힌 자국(주름)을 정확히 90도 직각으로 벌린다. 그러면 띠는 단위 길이의 선분들이 직각으로 이어진 경로가 된다.

펼친 띠의 왼쪽 끝을 원점 $(0,0)$에 두고, 첫 번째 직각이 $(1,0)$에 오도록 한다. 접는 순서와 종이 위의 한 위치가 주어질 때, 그 위치의 좌표를 구하라.

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 한 줄로 이루어지며, 문자 U와 L로 된 문자열과 정수 $m$이 차례로 주어진다. 문자열은 접는 순서를 왼쪽에서 오른쪽으로 나타내며, 그 길이 $n$은 $1 \le n \le 30$을 만족한다.

$n$번 접었다가 펼치면 띠는 $2^n$개의 단위 선분으로 나뉘고, 그 사이에 $2^n - 1$개의 직각이 생긴다. $m$은 종이 위의 위치를 가리킨다.

• $m = 0$은 왼쪽 끝으로, $(0,0)$이다.
• $m = 2^n$은 띠의 오른쪽 끝이다.
• $1 \le m \le 2^n - 1$인 $m$은 직각을 가리킨다. 왼쪽 끝에서부터 세어 $m = 1$은 첫 번째 직각($(1,0)$), $m = 2$는 두 번째 직각, ... 이다.

각 테스트 케이스마다 $m$이 가리키는 위치의 좌표를 (x,y) 형식으로 한 줄에 출력한다.