Background

Original link: https://oier.team/problems/X7G.

There is now a sequence.

The $1$st term of this sequence is $0$, the $2$nd term is $1$, the $3$rd term is $1$, and the $4$th term is $3$.

Now @lxwtr asks you what the value of the $n$-th term is.

Problem Description

Alice and Bob found a chessboard. The chessboard can be viewed as a number line. Initially, there are $n$ pieces at the origin. Let $a_i$ denote the number of pieces at position $i$ on the number line (the origin is $i=0$). Each time, the player finds the smallest $i$ such that $a_i\ge 2$, decreases $a_i$ by $2$, and then chooses either to increase $a_{i+1}$ by $1$ or to increase $a_{i+2}$ by $1$. Alice moves first, and they take turns operating. A player must make a move; if no such $i$ can be found, the game ends immediately.

Alice wants the total number of moves made by both players to be as small as possible, while Bob wants the total number of moves made by both players to be as large as possible. Both players are perfectly smart. They played $T$ games in total, and you want to know, for each game, how many moves in total will be made in the end.

Input Format

The first line contains a positive integer $T$, representing the number of games played.

The next $T$ lines each contain a positive integer $n$, representing the number of pieces at the origin at the start of each game.

Output Format

Output $T$ lines. The $i$-th line contains a non-negative integer, representing the total number of moves made by both players in the $i$-th game.

6
1
2
3
4
100
100000

0
1
1
3
95
99989

Hint

Sample Explanation

For the first game, the number of pieces at the origin is $1$, so no move can be made.

For the second game, exactly one move can be made, after which $a_1=1$ or $a_2=1$. Either way, no further move can be made.

For the third game, it is similar to the second game, except that one extra piece is left at the origin.

For the fourth game, no matter where Alice places the piece after the first move, Bob can place it at the same position, so Alice will make one more move. There are $3$ moves in total.

Constraints

This problem uses bundled testdata.

• Subtask 1 (5 points): $n\le16$.
• Subtask 2 (6 points): $n\le 50$.
• Subtask 3 (14 points): $n\le 200$.
• Subtask 4 (20 points): $n\le 5000$.
• Subtask 5 (21 points): $n\le 10^5$.
• Subtask 6 (34 points): no special properties.

For all testdata, $1\le T\le 500$, $1\le n\le 10^{18}$.

Translated by ChatGPT 5