Many Prizes (Small)

A tournament runs with $2^N$ teams, and $P$ identical prizes go to the teams that finish in places $0$ through $P-1$.

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

The tournament list is an ordering of all $2^N$ teams in the tournament. That order decides which teams meet, and in which round.

How the tournament runs

The tournament has $N$ rounds. Each team keeps a record, the results of the games it has played so far. A team that won its first game, lost its second and won its third has the record [W, L, W]. A team that has played no games has an empty record.

In each round, every team plays one game against a team with the same record. Among the teams with a given record, the first in the tournament list plays the second, the third plays the fourth, and the rest pair up the same way.

After $N$ rounds every team has a different record. Teams are ranked in reverse lexicographic order of their records, so [W, W, W] > [W, W, L] > [W, L, W] > ... > [L, L, L].

Here is how a tournament with $N = 3$ and the tournament list 2, 4, 5, 3, 6, 7, 1, 0 plays out.

Round 1   2 vs 4 (2 wins)   5 vs 3 (3 wins)   6 vs 7 (6 wins)   1 vs 0 (0 wins)

Round 2   record [W]: 2 vs 3 (2 wins)   6 vs 0 (0 wins)
          record [L]: 4 vs 5 (4 wins)   7 vs 1 (1 wins)

Round 3   record [W,W]: 2 vs 0 (0 wins)
          record [W,L]: 3 vs 6 (3 wins)
          record [L,W]: 4 vs 1 (1 wins)
          record [L,L]: 5 vs 7 (5 wins)

Final     place 0: team 0 [W,W,W]    place 4: team 1 [L,W,W]
          place 1: team 2 [W,W,L]    place 5: team 4 [L,W,L]
          place 2: team 3 [W,L,W]    place 6: team 5 [L,L,W]
          place 3: team 6 [W,L,L]    place 7: team 7 [L,L,L]

With $N = 3$ and $P = 4$, this list gives the prizes to teams 0, 2, 3 and 6. The list shows an ordering in which team 1 misses a prize, and team 0 takes a prize under every ordering, so the largest-numbered team that always takes a prize is team 0. The same list shows that team 6 can take a prize, and team 7 takes one under no ordering, so the largest-numbered team that could take a prize is team 6.

Given $N$ and $P$, find the largest-numbered team that takes a prize whatever the tournament list is, and the largest-numbered team that takes a prize for at least one tournament list.

The first line has the number of test cases $T$. Each of the next $T$ lines has two integers $N$ and $P$ separated by a space. The tournament has $2^N$ teams and $P$ prizes.

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

For each test case print one line in the form "Case #x: y z", where $x$ is the test case number starting from $1$, $y$ is the largest-numbered team that takes a prize whatever the tournament list is, and $z$ is the largest-numbered team that takes a prize for some tournament list.