부하 테스트

이제 여러분은 Code Jam에서 우승하여 Google에 소프트웨어 엔지니어로 채용되었고, Google의 엄청난 인기를 누리는 프로그래밍 대회 웹사이트에서 일하도록 배정되었다.

Google은 내년 Code Jam에 많은 참가자(P)가 참여할 것으로 예상하며, 사이트가 그만큼 많은 사람을 동시에 지원할 수 있는지 확인하려 한다. Code Jam 2010 동안 사이트가 오류 없이 동시에 적어도 L명을 지원할 수 있다는 것을 알아냈지만, 사이트가 아직 P명을 지원할 수 없다는 것도 알고 있다.

기계가 얼마나 더 필요한지 판단하기 위해, 사이트가 몇 명을 지원할 수 있는지를 C배 이내의 범위로 알고자 한다. 이는 사이트가 a명을 지원할 수 있다는 것은 알지만 a * C명은 지원할 수 없다는 것을 아는 어떤 정수 a가 존재한다는 뜻이다.

일련의 부하 테스트를 실행할 수 있으며, 각 테스트에서는 여러분이 선택한 어떤 정수 X에 대해 사이트가 적어도 X명을 지원할 수 있는지를 판정한다. 이전 테스트의 결과에 따라 실행할 테스트를 선택하는 최적의 전략을 사용한다면, 최악의 경우 몇 번의 부하 테스트가 필요한가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 1000. 2 ≤ C ≤ 10. L, P, C는 모두 정수이다.

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

1 ≤ L < P ≤ $10^{3}$.

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

1 ≤ L < P ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 공백으로 구분된 정수 L, P, C가 이 순서대로 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 케이스 번호이고, y는 사이트가 몇 명을 지원할 수 있는지를 C배 이내의 범위로 알게 되기 전까지 최악의 경우 실행해야 하는 부하 테스트의 횟수이다.

설명

케이스 #2에서는 사이트가 19명에서 57명 사이를 지원할 수 있다는 것을 이미 알고 있다. 두 수는 3배 차이이므로 테스트를 전혀 할 필요가 없다.

케이스 #4에서는 48명을 테스트할 수 있다. 하지만 사이트가 48명을 지원할 수 있다면 48*2 < 97이므로 테스트를 더 해야 한다. 49명을 테스트할 수도 있다. 하지만 사이트가 49명을 지원할 수 없다면 24 * 2 < 49이므로 테스트를 더 해야 한다. 따라서 두 번의 테스트가 필요하다.