Alice and Bob's Chessboard Game

Alice and Bob have discovered a special chessboard which can be regarded as a number line. Initially, there are (n) pieces at the origin (i.e. at position 0). Let (a_i) denote the number of pieces at position (i) (with (i=0) corresponding to the origin).

The rules of the game are as follows:

1. In each turn, the current player finds the smallest index (i) such that (a_i \ge 2).
2. They remove two pieces from (a_i) (i.e. set (a_i = a_i - 2)), and then add one piece to either (a_{i+1}) or (a_{i+2}).
3. Players alternate turns (Alice moves first) and each must perform a move if one is available. The game ends immediately when there is no index with (a_i \ge 2).

Alice wishes to minimize the total number of moves made by both players, while Bob wishes to maximize it. Both players are perfectly rational and play optimally. Given (T) independent games (each starting with a given value of (n)), you are to determine the total number of moves made in each game when both players play optimally.

It turns out that an invariant of the game is that every move reduces the total number of pieces by one. If the game ends with a configuration in which each position contains at most one piece, then the number of moves played is (n - k) where (k) is the total number of pieces in the final configuration. Under optimal play, it can be shown that (k) is exactly the number of ones in the binary representation of (n). Therefore, the answer for each game is [ \text{moves} = n - \mathrm{popcount}(n), ] where (\mathrm{popcount}(n)) denotes the number of 1's in the binary representation of (n).

Note: All formulas are rendered in (\LaTeX) format.

inputFormat

The first line contains a single integer \(T\) — the number of games.

Each of the next \(T\) lines contains a single integer \(n\) representing the initial number of pieces at the origin for that game.

outputFormat

For each test case, output a single integer — the total number of moves made in the game when both players play optimally.

Hint: The answer is \(n - \mathrm{popcount}(n)\).

sample

5
1
2
3
4
6

0
1
1
3
4