Dedenne

Have you ever heard about the famous Dedenne antennas? They allow Dedenne to communicate with each other even when they are miles and miles apart. However, Dedenne suspects that they do not communicate in an optimal way. That is why Dedenne came to you to optimize their language.

The language used by Dedenne consists of $n$ words. To transmit a word, Dedenne first uses a memorized dictionary to convert the word into a non-empty binary string (a codeword), and then transmits that string. The recipient receives the sequence and uses the same dictionary to recover the word. To preserve the correctness of the transmission, no two codewords in the dictionary may be equal, and no string may be a prefix of any other string.

Because of the peculiar nature of Dedenne, codewords are not allowed to have two consecutive 0 bits. When transmitted, two consecutive 0 bits merge into $\infty$ and hang up the transmitter indefinitely.

The dictionary is quite painful to memorize. Formally, let $C(s)$ be the cost of a binary string $s$. If $s$ is a prefix of exactly $k$ codewords, then $C(s)=\sum_{j=1}^{k}\lfloor 1+\log_2 j\rfloor$ The cost to memorize the dictionary is the sum of $C(s)$ over all binary strings $s$ that are a prefix of at least one codeword.

For example, take the dictionary with 4 codewords: 0, 10, 110, 111. The cost of memorizing it is $C(\varepsilon)+C(0)+C(1)+C(10)+C(11)+C(110)+C(111)=8+1+5+1+3+1+1=20$. Here $\varepsilon$ denotes the empty string.

What is the minimum possible cost of memorizing a dictionary of $n$ words?

The first line contains a single integer $t$ ($1 \le t \le 50\,000$), the number of independent test cases. Each of the following $t$ lines contains one integer $n$ ($2 \le n \le 10^{15}$), the number of words Dedenne needs to memorize.

For each test case, output a single integer: the minimum cost of a dictionary of $n$ words.

Here is a dictionary that might be used by Dedenne for $n = 10$ to minimize the cost of memorizing.