Кабинки в уборной
В уборной в ряд стоят n + 2 кабинок. Кабинки на левом и правом концах постоянно заняты охранниками. Другие n кабинок предназначены для пользователей.
Всякий раз, когда кто-то входит в ванную, он старается выбрать кабинку, максимально удаленную от других людей. Чтобы избежать путаницы, они следуют определенным правилам: для каждой пустой кабинки s вычисляются два значения l[s] и r[s], каждое из которых является числом пустых кабинок между s и ближайшей занятой кабинкой слева и справа соответственно. Затем рассматривается множество кабинок с самым дальним ближайшим соседом, то есть теми s, для которых min(l[s], r[s]) является максимальным. Если такая кабинка единственна, то выбирается именно она; в противном случае выбирается та из кабинок, где max(l[s], r[s]) является максимальным. Если и таких кабинок окажется несколько, то выбирается самая левая из них.
k людей собираются войти в уборную. Каждый выбирает себе кабинку до прихода следующего человека. Никто никогда не уходит.
Когда последний человек выбирает свою кабинку s, чему равно значение max(l[s], r[s]) и min(l[s], r[s])?
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Далее следуют t строк. Каждая строка содержит два целых числа n (1 ≤ n ≤ 10^18) и k (1 ≤ k ≤ n).
Выходные данные
Для каждого теста выведите одну строку содержащую Case #x: y z, где x номер теста (начиная с 1), y равно max(l[s], r[s]), z равно min(l[s], r[s]) - эти значения подсчитаны для последнего человека, вошедшего в уборную и выбравшего кабинку s.