화장실 칸

어떤 화장실에는 한 줄로 배치된 N + 2개의 칸이 있다. 왼쪽 끝과 오른쪽 끝의 칸은 화장실 경비원이 항상 차지하고 있다. 나머지 N개의 칸은 이용자를 위한 것이다.

누군가 화장실에 들어올 때마다 다른 사람들로부터 가능한 한 멀리 떨어진 칸을 고르려고 한다. 혼란을 피하기 위해 다음과 같은 결정론적 규칙을 따른다. 각 빈칸 S에 대해 두 값 $L_{S}$와 $R_{S}$를 계산하며, 이들은 각각 S와 왼쪽 또는 오른쪽에서 가장 가까운 사용 중인 칸 사이에 있는 빈칸의 수이다. 그런 다음 가장 가까운 이웃이 가장 멀리 있는 칸들의 집합, 즉 min($L_{S}$, $R_{S}$)가 최대인 S들을 고려한다. 그런 칸이 하나뿐이면 그 칸을 고른다. 그렇지 않으면 그중 max($L_{S}$, $R_{S}$)가 최대인 칸을 고른다. 그래도 동률인 칸이 여러 개라면 그중 가장 왼쪽 칸을 고른다.

K명이 화장실에 들어오려고 한다. 각 사람은 다음 사람이 도착하기 전에 자신의 칸을 고른다. 누구도 나가지 않는다.

마지막 사람이 자신의 칸 S를 골랐을 때, max($L_{S}$, $R_{S}$)와 min($L_{S}$, $R_{S}$)의 값은 무엇인가?

제한

1 ≤ T ≤ 100. 1 ≤ K ≤ N. 시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB.

작은 데이터 세트 1 (테스트 세트 1 - 공개)

1 ≤ N ≤ 1000.

작은 데이터 세트 2 (테스트 세트 2 - 공개)

1 ≤ N ≤ $10^{6}$.

큰 데이터 세트 (테스트 세트 3 - 비공개)

1 ≤ N ≤ $10^{18}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 각각 하나의 테스트 케이스가 주어진다. 각 줄에는 위에서 설명한 두 정수 N과 K가 주어진다.

각 테스트 케이스마다 Case #x: y z를 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y는 화장실에 마지막으로 들어온 사람이 자신이 고른 칸 S에 대해 계산한 max($L_{S}$, $R_{S}$)이며, z는 그 사람이 계산한 min($L_{S}$, $R_{S}$)이다.

예제 케이스 #1에서 첫 번째 사람은 가운데 두 칸 중 왼쪽 칸을 차지하여 다음과 같은 배치를 남긴다(O는 사용 중인 칸을, .는 빈칸을 나타낸다): O.O..O. 그다음 두 번째이자 마지막 사람은 바로 오른쪽 칸을 차지하여 한쪽에는 빈칸 1개를 남기고 다른 쪽에는 하나도 남기지 않는다.

예제 케이스 #2에서 첫 번째 사람은 가운데 칸을 차지하여 O..O..O가 된다. 그다음 두 번째이자 마지막 사람은 가장 왼쪽 칸을 차지한다.

예제 케이스 #3에서 첫 번째 사람은 가운데 두 칸 중 왼쪽 칸을 차지하여 O..O...O를 남긴다. 그다음 두 번째 사람은 연속된 빈칸 세 개의 가운데 칸을 차지한다.

예제 케이스 #4에서는 어떤 칸을 선택하더라도 마지막에는 모든 칸이 사용 중이다.

예제 케이스 #5에서 첫 번째이자 유일한 사람은 가운데 칸들 중 가장 왼쪽 칸을 고른다.