재입력

프로그래밍 대회를 위해 여러 시간 동안 공부한 뒤, 휴식을 취하며 비디오 게임을 하기로 했다. 현재 Quick Start라는 어드벤처 게임을 하고 있다.

이 게임에는 N개의 레벨이 있으며, 현재 K번째 레벨에 있다. 안타깝게도 마지막 레벨의 보스를 물리치려면 레벨 S에서 획득할 수 있는 특별한 검이 필요하다는 사실을 방금 깨달았다. 그 레벨은 이미 완료했지만, 그곳에서 검을 획득하는 것을 잊었다.

이제 검을 획득하고 가능한 한 가장 짧은 시간 안에 게임을 끝내려고 하며, 이를 위한 선택지는 두 가지이다.

• 게임을 다시 시작하고 레벨 1부터 모든 레벨을 다시 완료한다.

• 레벨 S에 도달할 때까지 이전 레벨로 이동하고, 검을 획득한 뒤 레벨 S부터 남은 모든 레벨을 완료한다.

레벨에 들어갈 때마다, 그 레벨을 완료하고 다음 레벨로 가거나, 이전 레벨로 이동하거나, 게임을 끝내거나 / 종료하는 방식 중 하나로 반드시 그 레벨에서 나가야 한다. 어떤 레벨에서든 나가는 데는 1분이 걸린다. 즉, 예를 들어 처음 L개의 레벨을 완료하는 데 L분이 걸렸다.

해야 할 일은 이미 사용한 시간을 포함하여 게임을 끝내는 데 필요한 총시간이 가장 짧아지는 선택지를 알아내는 것이다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ S < K < N.

테스트 세트 1

N ≤ 1000.

테스트 세트 2

N ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄이자 유일한 줄에는 세 정수 N, K, S가 주어진다. 각각 게임의 레벨 수, 현재 있는 레벨, 검을 획득해야 하는 레벨을 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 게임을 끝내는 데 필요한 최소 총시간이다.

예제 케이스 #1에서는 처음 4개의 레벨을 완료하고 5번째 레벨에 들어가는 데 4분이 걸렸다. 게임을 다시 시작하고 모든 레벨을 다시 완료하면 11분이 더 걸린다(다시 시작하는 데 1분, 10개의 레벨을 완료하는 데 10분). 따라서 총 15분이 걸린다. 다른 선택지는 레벨 2에 도달할 때까지 뒤로 이동하고(여기에 3분이 걸린다), 이후 남은 모든 레벨을 완료하는 것이다(여기에 9분이 더 걸린다). 그러면 총 16분이 걸린다.

예제 케이스 #2에서는 처음 6개의 레벨을 완료하고 7번째 레벨에 들어가는 데 6분이 걸렸다. 레벨 6에 도달할 때까지 뒤로 이동하고(일 분), 이후 남은 모든 레벨을 완료하면(5분) 게임을 끝내는 데 총 12분이 걸린다.