# Data structures contest - high level

# Bathroom Stalls

A certain bathroom has **n** + **2** stalls in a single row; the stalls on the left and right ends are permanently occupied by the bathroom guards. The other **n** stalls are for users.

Whenever someone enters the bathroom, they try to choose a stall that is as far from other people as possible. To avoid confusion, they follow deterministic rules: For each empty stall **s**, they compute two values `l`

and _{s}`r`

, each of which is the number of empty stalls between _{s}**s** and the closest occupied stall to the left or right, respectively. Then they consider the set of stalls with the farthest closest neighbor, that is, those **s** for which min(`l`

, _{s}`r`

) is maximal. If there is only one such stall, they choose it; otherwise, they choose the one among those where max(_{s}`l`

, _{s}`r`

) is maximal. If there are still multiple tied stalls, they choose the leftmost stall among those._{s}

**k** people are about to enter the bathroom; each one will choose their stall before the next arrives. Nobody will ever leave.

When the last person chooses their stall **s**, what will the values of max(`l`

, _{s}`r`

) and min(_{s}`l`

, _{s}`r`

) be?_{s}

#### Input

The first line gives the number of test cases **t** (**1** ≤ **t** ≤ **100**). **t** lines follow. Each line describes a test case with two integers **n** (**1** ≤ **n** ≤ `10`

) and ^{18}**k** (**1** ≤ **k** ≤ **n**) as described above.

#### Output

For each test case, output one line containing **Case #x: y z**, where **x** is the test case number (starting from **1**), **y** is max(`l`

, _{s}`r`

), and _{s}**z** is min(`l`

, _{s}`r`

) as calculated by the last person to enter the bathroom for their chosen stall _{s}**s**.

5 4 2 5 2 6 2 1000 1000 1000 1

Case #1: 1 0 Case #2: 1 0 Case #3: 1 1 Case #4: 0 0 Case #5: 500 499