부하 테스트 (작은 입력)

내년 프로그래밍 대회 사이트에 참가자 $P$명이 몰릴 예정이다. 사이트가 그만큼의 동시 접속을 견디는지 미리 확인해야 한다.

지난 대회에서 사이트가 오류 없이 동시에 최소 $L$명을 처리한다는 사실이 확인되었다. 그리고 $P$명은 아직 처리하지 못한다는 것도 알고 있다.

기계를 몇 대 더 준비해야 할지 판단하려면 사이트가 감당하는 인원을 $C$배 이내의 오차로 알아야 한다. 즉 사이트가 $a$명은 감당하고 $a \times C$명은 감당하지 못한다는 것을 아는 정수 $a$를 찾아야 한다.

부하 테스트를 여러 번 실행할 수 있다. 한 번의 부하 테스트는 직접 고른 정수 $X$에 대해 사이트가 최소 $X$명을 감당하는지 아닌지를 알려 준다. 앞선 테스트 결과를 보고 다음에 실행할 테스트를 고를 수 있다.

최적으로 전략을 세울 때, 최악의 경우 부하 테스트를 몇 번 실행해야 하는지 구하여라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

이어지는 $T$개의 줄에 각각 정수 $L$, $P$, $C$가 이 순서대로 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 1000$
• $1 \le L < P \le 1000$
• $2 \le C \le 10$
• $L$, $P$, $C$는 모두 정수이다.

각 테스트 케이스마다 한 줄에 Case #x: y 형식으로 출력한다. $x$는 1부터 시작하는 케이스 번호이고, $y$는 사이트가 감당하는 인원을 $C$배 이내의 오차로 알아내기까지 최악의 경우 실행해야 하는 부하 테스트의 횟수이다.

$L = 19$, $P = 57$, $C = 3$이면 사이트가 19명은 감당하고 57명은 감당하지 못한다는 것을 이미 알고 있다. 두 값이 정확히 3배 차이이므로 테스트가 필요하지 않다.

$L = 24$, $P = 97$, $C = 2$이면 먼저 48을 테스트해 볼 수 있다. 사이트가 48명을 감당한다면 $48 \times 2 < 97$이므로 테스트가 더 필요하다. 대신 49를 테스트할 수도 있다. 사이트가 49명을 감당하지 못한다면 $24 \times 2 < 49$이므로 역시 테스트가 더 필요하다. 어느 쪽을 고르든 최악의 경우 두 번이 필요하다.