알레르기 검사

Kelly는 N개의 음식 중 정확히 하나에 알레르기가 있지만, 어느 것인지는 확실히 알지 못한다. 그래서 이를 알아내기 위해 몇 가지 실험을 하기로 한다.

각 실험에서 Kelly는 여러 음식을 골라 모두 먹는다. 알레르기 반응이 나타나는지 확인하기 위해 A일을 기다린다. 반응이 나타나지 않으면 자신이 먹은 음식 중 어느 것에도 알레르기가 없다는 것을 알게 된다. 반응이 나타나면 그 반응이 사라질 때까지 기다려야 한다. 여기에는 음식을 먹은 순간부터 총 B일이 걸린다.

실험을 단순화하기 위해 Kelly는 각 실험이 끝날 때까지(A일 또는 B일 후) 기다린 다음 다음 실험을 시작하기로 한다. 각 실험을 시작할 때 이전 실험의 결과에 따라 먹고 싶은 음식의 집합을 선택할 수 있다.

Kelly는 N개의 음식 중 어느 것에 알레르기가 있는지 알게 되기까지 걸리는 최악의 경우의 일수를 최소화하도록 각 실험에서 먹을 음식을 선택한다. 최악의 경우에는 얼마나 걸리는가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 200.

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ $10^{15}$. 1 ≤ A ≤ B ≤ 100.

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ $10^{15}$. 1 ≤ A ≤ B ≤ $10^{12}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄에 주어지며, 공백으로 구분된 세 정수 N, A, B를 포함한다.

각 테스트 케이스마다 "Case #x: y"을 담은 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 Kelly가 최악의 경우에 자신이 어느 음식에 알레르기가 있는지 알아내는 데 걸리는 일수이다.

첫 번째 예제 케이스에서는 다음과 같다.

• 먼저 Kelly는 음식 #1과 #2를 먹는다.

• 5일 후에도 반응이 나타나지 않으면 음식 #3를 먹는다. 그로부터 5일 후에는 자신이 음식 #3에 알레르기가 있는지, 아니면 음식 #4에 알레르기가 있는지 알게 된다.

• 첫 번째 실험에서 반응이 나타나면 첫 번째 실험으로부터 7일 후에 음식 #1를 먹는다. 그로부터 5일 후에는 자신이 음식 #1에 알레르기가 있는지, 아니면 음식 #2에 알레르기가 있는지 알게 된다.