Total Books Promotion

A customer is offered a special promotion when purchasing books. For each purchase of n books, the customer receives additional free books. The number of free books is determined by the formula:

\(2^{k}\) where \(k = \lfloor \log_{2} n \rfloor\).

In other words, \(k\) is the greatest integer such that \(2^k \le n\), and the total number of books given to the customer is:

\(total = n + 2^{\lfloor \log_{2} n \rfloor}\).

Your task is to compute the total number of books the customer receives given the number of books purchased.

inputFormat

The first line of input contains an integer t (1 ≤ t ≤ 10), the number of test cases.

Each of the following t lines contains a single integer n (1 ≤ n ≤ 10⁹), representing the number of books purchased.

outputFormat

For each test case, output a single line containing the total number of books the customer will receive (purchased books plus free books).

## sample

1
1

2

</p>