많은 상품

2^{N}개의 팀이 참가하는 토너먼트를 열고, 순위가 0..P-1인 팀들에게 동일한 상품 P개를 수여하려고 한다.

팀에는 0부터 $2^{N}$-1까지 번호가 매겨져 있다. 팀 i와 팀 j가 서로 경기할 때, 팀 i는 i<j일 때, 그리고 그럴 때에만 승리한다.

토너먼트에 참가하는 팀들은 토너먼트의 토너먼트 목록이라고 하는 특정한 순서로 배치되며, 이 목록에는 토너먼트의 2^{N}개 팀이 모두 포함된다. 토너먼트 목록은 어떤 팀끼리 경기하는지와 그 경기 순서에 영향을 미친다.

해야 할 일은 토너먼트 목록의 순서와 관계없이 상품을 받을 것이 보장되는 팀 중 번호가 가장 큰 팀을 찾고, 토너먼트 목록의 순서에 따라 상품을 받을 수도 있는 팀 중 번호가 가장 큰 팀을 찾는 것이다.

Tournament Resolution

토너먼트는 N개의 라운드로 진행된다.

각 팀에는 지금까지 치른 경기 결과의 목록인 전적이 있다. 예를 들어 어떤 팀이 세 경기를 치러 첫 번째 경기에서 이기고, 두 번째 경기에서 지고, 세 번째 경기에서 이겼다면 그 팀의 전적은 [W, L, W]이다. 어떤 팀도 경기를 치르지 않았다면 그 팀의 전적은 []이다.

각 라운드에서 모든 팀은 자신과 전적이 같은 팀과 경기한다. 특정 전적을 가진 팀 중 토너먼트 목록에서 첫 번째인 팀은 해당 전적을 가진 두 번째 팀과 경기하고, 같은 전적을 가진 세 번째 팀은 네 번째 팀과 경기하는 식으로 계속된다.

After N개의 라운드가 끝나면 각 팀의 전적은 서로 다르다. 팀들은 전적의 역순 사전식 순서에 따라 순위가 정해지므로, [W, W, W] > [W, W, L] > [W, L, W] ... > [L, L, L].

다음은 N=3이고 토너먼트 목록이 [2, 4, 5, 3, 6, 7, 1, 0]인 토너먼트의 예제이다. 열은 서로 다른 라운드를 나타내며, 팀들은 전적에 따라 묶여 있다. 예제에서 각 경기의 승자는 *로 표시되어 있다.

Round 1    Round 2    Round 3    Final Result
                                 (best rank at top)
[]         [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]

4개의 상품을 (N=3, P=4) 수여하면, 상품은 팀 0, 2, 3, 그리고 6에게 돌아간다.

N=3, P=4일 때 토너먼트 목록의 순서와 관계없이 상품을 받을 것이 보장된 팀 중 번호가 가장 큰 팀은 0였다. 이 토너먼트 목록은 팀 1가 상품을 받지 못할 수도 있음을 보여 주며, 실제로 팀 0는 토너먼트 목록의 순서와 관계없이 항상 상품을 받는다.

N=3, P=4일 때 토너먼트 목록의 순서에 따라 상품을 받을 수도 있는 팀 중 번호가 가장 큰 팀은 6였다. 이 토너먼트 목록은 팀 6가 상품을 받을 수도 있음을 보여 주며, 실제로 팀 7는 토너먼트 목록의 순서와 관계없이 절대로 상품을 받지 못한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ P ≤ $2^{N}$.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 10.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 50.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 N과 P로 구성된다. N은 토너먼트에 2^{N}개의 팀이 참가함을 나타내고, P는 상품의 개수이다.

각 테스트 케이스마다 "Case #x: y z"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 토너먼트 목록의 순서와 관계없이 상품을 받을 것이 보장되는 팀 중 번호가 가장 큰 팀이고, z는 토너먼트 목록의 순서에 따라 상품을 받을 수도 있는 팀 중 번호가 가장 큰 팀이다.