사탕 가게 (Large)

문제

사탕 가게를 잘 굴리려면 최적화할 일이 많다. 요즘 가장 잘 나가는 사탕은 휘즈바퍼인데, 이 사탕은 아주 빨리 상해서 다음 두 가지 제약이 붙는다.

매일 아침 공급처에서 휘즈바퍼를 새로 사 와야 한다.
그날 아침에 사 온 상자로만 휘즈바퍼를 팔아야 한다.

공급처에는 그램 단위의 정수 무게라면 어떤 무게의 상자든 주문할 수 있다. 상자를 뜯거나 나눌 수는 없으므로 손님에게는 언제나 상자를 통째로 건넨다.

하루에 손님이 최대 $k$ 명 온다. 손님은 첫 번째 사람부터 차례로 $1$ 센트 이상 $C$ 센트 이하의 정수 금액을 정하고, 그 금액만큼 사탕을 사 간다. 사탕은 $1$ 그램에 $1$ 센트로 파니까 $4$ 센트를 쓰겠다는 손님에게는 정확히 $4$ 그램을 건네야 한다. $4$ 그램 상자 하나를 건네도 되고, $2$ 그램 상자 하나와 $1$ 그램 상자 두 개를 건네도 된다.

손님이 각각 얼마를 부르든 모든 손님에게 원하는 무게를 정확히 건네려면, 아침에 주문할 상자는 최소 몇 개인가?

참고: 손님은 금액을 정할 때 앞선 손님이 무엇을 사 갔는지는 알지만, 뒤에 올 손님이 무엇을 살지는 알 수 없다.

예를 들어 하루에 손님이 최대 두 명 오고 각자 최대 $2$ 센트를 쓴다면( $k=2$ , $C=2$ ) $1$ 그램 상자 네 개를 주문해도 되지만, $1$ 그램 상자 두 개와 $2$ 그램 상자 한 개, 즉 세 개면 충분하다. 배분은 아래처럼 하면 된다.

첫 번째 손님	건네는 상자	두 번째 손님	건네는 상자
2센트	2그램 한 개	2센트	1그램 두 개
2센트	2그램 한 개	1센트	1그램 한 개
1센트	1그램 한 개	2센트	2그램 한 개
1센트	1그램 한 개	1센트	1그램 한 개

첫 손님이 무엇을 고르든 두 번째 손님까지 정확한 무게를 건넬 수 있으므로, $k=2$ , $C=2$ 에서는 상자 세 개로 모든 주문 순서를 감당한다. $k=1$ , $C=5$ 라면 $1$ 그램 상자 한 개와 $2$ 그램 상자 두 개로 충분하다.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에 각각 두 정수 $k$ 와 $C$ 가 공백으로 구분되어 주어진다. $k$ 는 하루에 오는 손님 수의 최대치이고, $C$ 는 손님 한 명이 쓸 수 있는 금액의 최대치다.

제한

$1 \le T \le 100$
$1 \le k \le 1000$
$1 \le C \le 10^{12}$

출력

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$ 는 $1$ 부터 시작하는 테스트 케이스 번호이고, $y$ 는 매일 아침 주문해야 하는 상자의 최소 개수다.