Many prizes

You run a tournament with $2^N$ teams. The teams that finish in ranks 0 through $P-1$ each receive one identical prize.

The teams are numbered 0 through $2^N - 1$. When team $i$ plays team $j$, team $i$ wins if and only if $i < j$.

An ordering of all $2^N$ teams in a single line is called a tournament list. The tournament list decides which teams meet and when.

Find two numbers. First, the largest-numbered team that wins a prize no matter how the tournament list is ordered. Second, the largest-numbered team that wins a prize for at least one ordering of the tournament list.

How the tournament runs

The tournament has $N$ rounds.

Each team carries a record, the results of its games so far in order. For example, a team that has played three games and won the first, lost the second and won the third has record [W, L, W]. A team that has played no games has record [].

In every round each team plays one game against a team with the same record. Among the teams with a given record, the first and the second in the tournament list meet, the third and the fourth meet, and so on.

After $N$ rounds every team has a different record. Records are compared lexicographically with W ahead of L, and a larger record gets a better rank, so [W, W, W] > [W, W, L] > [W, L, W] > ... > [L, L, L].

Here is a tournament with $N = 3$ and the tournament list [2, 4, 5, 3, 6, 7, 1, 0]. Each column is one round, teams are grouped by their record, and the winner of each game is marked with *. The last column is the final ranking, best rank on top.

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]

With $N = 3$ and $P = 4$, the prizes go to teams 0, 2, 3 and 6.

For $N = 3$ and $P = 4$, the largest-numbered team that wins a prize regardless of the tournament list is team 0. The list above shows that team 1 can miss a prize, and team 0 wins one under every ordering.

For $N = 3$ and $P = 4$, the largest-numbered team that can win a prize for some tournament list is team 6. The list above shows team 6 winning a prize, and team 7 never wins one under any ordering.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case is two space separated integers $N$ and $P$: the tournament has $2^N$ teams and $P$ prizes.

Limits

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

For each test case, print one line in the form Case #x: y z. Here $x$ is the test case number starting from 1, $y$ is the largest-numbered team that wins a prize regardless of the tournament list, and $z$ is the largest-numbered team that wins a prize for at least one tournament list.