[2019 SCPC 1차 예선]

오르락 내리락

\(1\) 이상의 정수를 받아서 다음의 규칙에 따른 “작업”을 반복하여 결국 \(1\) 을 만드는 게임을 하려고 한다.

아래 규칙은 한번의 작업에 대한 것이고, 작업의 결과로 만들어지는 수에 작업을 수행하는 것을 반복한다. 규칙에도 나와 있듯이 현재 수가 \(1\) 인 경우는 작업을 하지 않고 멈춘다.



  1. 만약 수가 \(1\) 이면 작업을 하지 않고 멈춘다.

  2. 만약 수가 \(1\) 이 아닌 홀수이면 \(1\) 을 더한다.

  3. 만약 수가 짝수이면 \(2\) 로 나눈다.



예를 들어, 받은 수가 \(2\) 인 경우는 \(2\rightarrow1\) 로 \(1\) 회의 작업 후에 멈춘다.

받은 수가 \(4\) 인 경우는 \(4→2→1\) 로 \(2\) 회의 작업 후에 멈춘다.

받은 수가 \(3\) 인 경우는 \(3→4→2→1\) 로 \(3\) 회의 작업 후에 멈춘다.

받은 수가 \(6\) 인 경우는 \(6→3→4→2→1\) 로 \(4\) 회의 작업 후에 멈춘다.



앞의 예 들에서 볼 수 있듯이, 받은 수가 \(3\) 인 경우의 작업 횟수를 알면 받은 수가 \(6\)인 경우의 작업 횟수를 바로 계산할 수 있다는 것을 알 수 있다.



두 정수 \(N_1\)과 \(N_2\)를 입력으로 받아서 (\(1≤N_1≤N_2≤10^6\)), \(N_1,N_1+1,N_1+2,…,N_2\)의 작업 회수를 모두 더한 값을 계산하는 프로그램을 작성하라.






입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,

이후 차례로  \(T\) 개의 테스트 케이스가 주어진다. (\(1 ≤ T ≤ 10,000\)) 

각 테스트 케이스의 첫 줄에는 정수 \(N_1\)과 \(N_2\)가 주어진다. (\(1≤N_1≤N_2≤10^6\))


출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 \(C\)는 테스트 케이스의 번호이다.

그 다음 줄에, \(N_1,N_1+1,N_1+2,…,N_2\)의 작업 회수를 모두 더한 값을 출력한다.

입출력예

입력
2
3 6
6 6
출력
Case #1
14
Case #2
4

돌아가기


댓글