이분 탐색의 효율을 의심한 학생

이분 탐색은 컴퓨터 과학의 고전적인 알고리즘이다. 이 문제에서는 다음 의사 코드를 이분 탐색의 정의로 삼는다.

배열 a의 a[0]부터 a[n-1]까지에서 값 x를 찾는다.
a의 값은 순증가한다고 가정한다.

    Low = 0
    High = n - 1
    While Low <= High
        Mid = (Low + High) / 2   [정수 나눗셈은 소수점 이하를 버린다]
        If a[Mid] = x then return FOUND
        If a[Mid] < x then Low = Mid + 1
        If a[Mid] > x then High = Mid - 1
    While 문을 빠져나오면 return NOT_FOUND

교수들은 이 알고리즘이 효율적이고, 최악의 경우 반복 횟수가 대략 $\log_2 n$이며 평균은 그보다 조금 적다고 가르친다. 이를 믿지 못한 학생이 여러 크기의 리스트를 만들어 리스트에 있는 모든 값을 찾아 보고, 반복문이 몇 번 실행되는지 세었다. 아래 리스트에서는 각 값을 찾는 데 실행된 반복 횟수를 그 값 아래에 적었다.

이 리스트의 총 반복 횟수는 17이다.

리스트가 정렬되어 있고 값이 모두 다르다면, 길이가 7인 리스트의 총 반복 횟수는 언제나 17이다. 즉 리스트의 길이가 총 반복 횟수를 결정한다.

리스트의 길이가 주어질 때 총 반복 횟수를 구하라. 입력에 있는 모든 테스트 케이스의 답은 부호 있는 64비트 정수에 들어간다.

입력에는 테스트 케이스가 여러 개 들어 있다. 각 테스트 케이스는 리스트의 길이인 양의 정수 $n$ 하나로 이루어진다. $2 < n < 10^7$이고, 테스트 케이스는 100개를 넘지 않는다. 테스트 케이스는 임의의 공백 문자로 구분된다. 파일의 끝을 만날 때까지 읽어서 처리한다.

각 테스트 케이스마다 길이가 $n$인 리스트에서 모든 값을 찾을 때의 총 반복 횟수를 출력한다. 형식은 다음을 정확히 따른다. "Case", 공백 한 칸, 테스트 케이스 번호, 콜론, 공백 한 칸, 그 테스트 케이스의 답이다. 답 뒤에는 공백을 붙이지 않는다.