В уборной в ряд стоят n + 2 кабинок. Кабинки на левом и правом концах постоянно заняты охранниками. Другие n кабинок предназначены для пользователей.

Всякий раз, когда кто-то входит в ванную, он старается выбрать кабинку, максимально удаленную от других людей. Чтобы избежать путаницы, они следуют определенным правилам: для каждой пустой кабинки s вычисляются два значения ls и rs, каждое из которых является числом пустых кабинок между s и ближайшей занятой кабинкой слева и справа соответственно. Затем рассматривается множество кабинок с самым дальним ближайшим соседом, то есть теми s, для которых min(ls, rs) является максимальным. Если такая кабинка единственна, то выбирается именно она; в противном случае выбирается та из кабинок, где max(ls, rs) является максимальным. Если и таких кабинок окажется несколько, то выбирается самая левая из них.

k людей собираются войти в уборную. Каждый выбирает себе кабинку до прихода следующего человека. Никто никогда не уходит.

Когда последний человек выбирает свою кабинку s, чему равно значение max(ls, rs) и min(ls, rs)?

Входные данные

Первая строка содержит количество тестов t (1 ≤ t ≤ 100). Далее следуют t строк. Каждая строка содержит два целых числа n (1 ≤ n ≤ 1018) и k (1 ≤ k ≤ n).

Выходные данные

Для каждого теста выведите одну строку содержащую Case #x: y z, где x номер теста (начиная с 1), y равно max(ls, rs), z равно min(ls, rs) - эти значения подсчитаны для последнего человека, вошедшего в уборную и выбравшего кабинку s.