여러 개의 상품

$2^N$개 팀이 참가하는 대회를 연다. 최종 순위 0위부터 $P-1$위까지의 팀은 똑같은 상품을 하나씩 받는다.

팀 번호는 0번부터 $2^N - 1$번까지다. $i$번 팀과 $j$번 팀이 맞붙으면 $i < j$일 때만 $i$번 팀이 이긴다.

대회에 참가하는 $2^N$개 팀을 모두 한 줄로 늘어놓은 순서를 대진표라고 한다. 대진표는 어떤 팀끼리 언제 맞붙는지를 결정한다.

구할 것은 두 가지다. 첫째, 대진표를 어떻게 짜도 상품을 받는 팀 중 번호가 가장 큰 팀. 둘째, 대진표를 잘 짜면 상품을 받을 수 있는 팀 중 번호가 가장 큰 팀.

대회 진행 방식

대회는 $N$개 라운드로 진행한다.

각 팀에는 지금까지 치른 경기 결과를 순서대로 적은 전적이 있다. 예를 들어 세 경기를 치러 첫 경기를 이기고, 두 번째 경기를 지고, 세 번째 경기를 이겼다면 전적은 [W, L, W]다. 아직 한 경기도 치르지 않았다면 전적은 []다.

매 라운드에서 모든 팀은 자신과 전적이 같은 팀과 한 경기씩 치른다. 전적이 같은 팀 중 대진표에서 첫 번째인 팀과 두 번째인 팀이 맞붙고, 세 번째인 팀과 네 번째인 팀이 맞붙는 식으로 짝을 짓는다.

$N$개 라운드가 끝나면 모든 팀의 전적이 서로 다르다. 전적은 사전순으로 비교하되 W가 L보다 앞선다고 보고, 앞선 전적일수록 높은 순위를 준다. 즉 [W, W, W] > [W, W, L] > [W, L, W] > ... > [L, L, L] 순이다.

다음은 $N = 3$이고 대진표가 [2, 4, 5, 3, 6, 7, 1, 0]인 대회의 예다. 각 열은 라운드 하나를 나타내고, 전적이 같은 팀끼리 묶여 있다. 각 경기의 승자에는 *를 붙였다. 마지막 열은 최종 순위이며 위쪽이 높은 순위다.

R1         R2         R3         Final
[]         [W]        [W,W]
2 *        2 *        2          0  [W,W,W]
4          3          0 *        2  [W,W,L]
                      [W,L]
5          6          3 *        3  [W,L,W]
3 *        0 *        6          6  [W,L,L]
           [L]        [L,W]
6 *        4 *        4          1  [L,W,W]
7          5          1 *        4  [L,W,L]
                      [L,L]
1          7          5 *        5  [L,L,W]
0 *        1 *        7          7  [L,L,L]

$N = 3$, $P = 4$로 상품을 4개 준다면 상품은 0번, 2번, 3번, 6번 팀이 받는다.

$N = 3$, $P = 4$일 때 대진표와 상관없이 상품을 받는 팀 중 번호가 가장 큰 팀은 0번이다. 위 대진표는 1번 팀이 상품을 받지 못하는 경우가 있음을 보여주고, 0번 팀은 대진표를 어떻게 짜도 반드시 상품을 받는다.

$N = 3$, $P = 4$일 때 대진표에 따라 상품을 받을 수 있는 팀 중 번호가 가장 큰 팀은 6번이다. 위 대진표는 6번 팀이 상품을 받는 경우를 보여주고, 7번 팀은 대진표를 어떻게 짜도 상품을 받지 못한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 $N$과 $P$로 이루어진다. 대회에는 $2^N$개 팀이 참가하고, 상품은 $P$개다.

제한

• $1 \le T \le 100$
• $1 \le N \le 50$
• $1 \le P \le 2^N$

각 테스트 케이스마다 Case #x: y z 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. $y$는 대진표와 상관없이 상품을 받는 팀 중 번호가 가장 큰 팀이고, $z$는 대진표에 따라 상품을 받을 수 있는 팀 중 번호가 가장 큰 팀이다.