알레르기 검사 (큰 입력)

켈리는 음식 $N$가지 중 정확히 하나에 알레르기가 있지만 어느 음식인지 모른다. 그래서 실험으로 알아내기로 했다.

한 번의 실험에서 켈리는 음식 몇 가지를 골라 모두 먹는다. 먹은 지 정확히 $A$일이 지나면 반응이 있었는지 알게 된다. 반응이 없었다면 그 실험에서 먹은 음식에는 알레르기가 없다. 반응이 있었다면 알레르기가 있는 음식은 그 안에 있고, 반응은 음식을 먹은 시점부터 $B$일이 지나야 가라앉는다.

켈리는 앞 실험이 완전히 끝난 뒤에야 다음 실험을 시작한다. 그래서 반응이 없던 실험은 $A$일, 반응이 있던 실험은 $B$일을 쓴다. 각 실험에서 무엇을 먹을지는 그때까지 나온 결과를 보고 정한다.

구하려는 값은 켈리가 알레르기가 있는 음식을 알아낼 때까지 걸린 날수다. 실험 결과는 먹은 지 $A$일 뒤에 나오므로, 마지막 실험에서 생긴 반응이 가라앉기를 기다릴 필요는 없다.

켈리는 최악의 경우 걸리는 날수가 가장 짧아지도록 실험을 고른다. 최악의 경우 며칠이 걸리는가?

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 세 정수 $N$, $A$, $B$가 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 200$
• $1 \le N \le 10^{15}$
• $1 \le A \le B \le 10^{12}$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 켈리가 최악의 경우 알레르기가 있는 음식을 알아내는 데 걸리는 날수다.

$N = 4$, $A = 5$, $B = 7$인 경우 답은 12다.

• 켈리는 먼저 1번 음식과 2번 음식을 먹는다.
• 5일이 지나도 반응이 없으면 3번 음식을 먹는다. 그로부터 5일 뒤에 3번과 4번 중 어느 쪽에 알레르기가 있는지 알게 되므로 이 갈래는 10일에 끝난다.
• 첫 실험에서 반응이 있으면 첫 실험이 시작된 지 7일 뒤에 1번 음식을 먹는다. 그로부터 5일 뒤에 1번인지 2번인지 알게 되므로 이 갈래는 12일에 끝난다.