사탕 가게

사탕 가게를 운영하는 것은 힘들다! 온갖 것을 최적화해야 한다. 최근에는 Whizboppers라는 매우 인기 있는 종류의 사탕을 판매하고 있다. 이 사탕은 매우 빨리 상하기 때문에 다음과 같은 특성이 있다.

• 매일 아침 공급업체로부터 새 Whizboppers를 구매해야 한다.

• 그날 아침 공급업체로부터 구매한 상자에 담긴 채로 Whizboppers를 판매해야 한다.

공급업체에는 정수 그램만큼의 사탕이 들어 있는 어떤 크기의 상자로도 Whizboppers를 주문할 수 있다.

매일 최대 k명이 가게를 방문하며, 첫 번째 사람부터 차례로 Whizboppers에 쓸 정수 센트 금액을 1센트 이상 C센트 이하에서 선택한다. Whizboppers는 그램당 1센트에 판매할 것이므로, 어떤 사람이 4센트를 쓰고 싶어 한다면 그 사람에게 정확히 4그램의 사탕을 준다. 이를 위해 그 사람에게 4그램 상자 하나를 줄 수도 있고, 또는 2그램 상자 하나와 1그램 상자 두 개를 줄 수도 있다.

각 사람이 얼마를 주문하더라도 항상 모든 사람에게 원하는 질량의 Whizboppers를 줄 수 있도록 주문해야 하는 상자의 최소 개수는 얼마인가?

참고: 어떤 사람이 구매할 사탕의 양을 선택할 때, 다른 사람들이 이미 무엇을 구매했는지는 알지만 이후 사람들이 무엇을 구매할지는 알 수 없다.

예를 들어, 매일 최대 2명이 가게를 방문하고 각자 최대 2센트를 쓴다면(k=2, C=2), 공급업체로부터 1그램 상자 네 개를 구매할 수 있다. 하지만 더 적게 구매할 수 있다. 1그램 상자 두 개와 2그램 상자 하나를 구매하면 손님들의 요구를 충족할 수 있다. 방법은 다음과 같다.

First Person   Boxes given   Second Person   Boxes given
--------------------------------------------------------
  2 cents      1 x 2-gram      2 cents       2 x 1-gram
                               1 cent        1 x 1-gram
  -----------------------------------------------------
  1 cent       1 x 1-gram      2 cents       1 x 2-gram
                               1 cent        1 x 1-gram

첫 번째 사람이 무엇을 주문하든, 두 번째 사람이 여전히 알맞은 양의 사탕을 받을 수 있도록 상자를 내줄 수 있다. 따라서 k=2, C=2인 경우 3개의 상자로 어떤 주문 순서에도 대응할 수 있다.

제한

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

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

1 ≤ k ≤ 20. 1 ≤ C ≤ 3.

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

1 ≤ k ≤ 1000. 1 ≤ C ≤ $10^{12}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 각각 두 정수 k와 C가 주어진다. 이는 각각 사람 수의 최댓값과 각 사람이 쓸 수 있는 센트 금액의 최댓값이다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 매일 주문해야 하는 상자의 최소 개수이다.

설명

첫 번째 케이스에서는 1그램 상자 하나와 2그램 상자 두 개를 구매할 수 있다. 두 번째 케이스에서는 1그램 상자 두 개와 2그램 상자 하나를 구매할 수 있다.