Dedenne

Dedenne의 유명한 안테나에 대해 들어 본 적이 있는가? 이 안테나 덕분에 Dedenne은 아주 멀리 떨어져 있어도 서로 통신할 수 있다. 하지만 Dedenne은 지금의 통신 방식이 최적이 아닐 것이라고 의심한다. 그래서 Dedenne은 언어를 최적화하려고 당신을 찾아왔다.

Dedenne이 사용하는 언어는 $n$개의 단어로 이루어져 있다. 단어를 전송하려면 Dedenne은 먼저 암기한 사전으로 단어를 비어 있지 않은 이진 문자열(코드워드)로 바꾼 뒤, 그 문자열을 전송한다. 수신자는 같은 사전을 사용해 단어를 복원한다. 전송이 올바르게 이루어지도록, 사전의 두 코드워드는 같을 수 없고 어떤 문자열도 다른 문자열의 접두사일 수 없다.

Dedenne의 특성상 코드워드에는 연속된 0 비트 두 개가 있을 수 없다. 전송할 때 연속된 0은 $\infty$로 합쳐져 송신기를 무기한 멈추게 한다.

사전은 외우기가 매우 번거롭다. 형식적으로, 이진 문자열 $s$가 정확히 $k$개의 코드워드의 접두사일 때 $s$의 비용을 $C(s)$라고 하자. 그러면 $C(s)=\sum_{j=1}^{k}\lfloor 1+\log_2 j\rfloor$ 이다. 사전을 외우는 비용은 적어도 하나의 코드워드의 접두사인 모든 이진 문자열 $s$에 대한 $C(s)$의 합이다.

예를 들어 코드워드가 0, 10, 110, 111인 네 개짜리 사전을 보자. 이 사전을 외우는 비용은 $C(\varepsilon)+C(0)+C(1)+C(10)+C(11)+C(110)+C(111)=8+1+5+1+3+1+1=20$이다. 여기서 $\varepsilon$은 빈 문자열이다.

$n$개의 단어를 담는 사전을 외우는 비용의 최솟값은 얼마인가?

첫 번째 줄에 독립된 테스트 케이스의 개수 $t$ ($1 \le t \le 50\,000$)가 주어진다. 이후 $t$개의 줄에는 각각 정수 $n$ ($2 \le n \le 10^{15}$) 하나가 주어진다. $n$은 Dedenne이 외워야 하는 단어의 수이다.

각 테스트 케이스마다 $n$개의 단어를 담는 사전의 외우기 비용 최솟값을 정수 하나로 출력한다.

아래 그림은 $n = 10$일 때 외우기 비용을 최소화하는 데 쓸 수 있는 사전이다.