P4461 [CQOI2018] Nine Linked Rings

The Nine Linked Rings is a traditional Chinese puzzle game. As shown in the figure, nine rings are looped onto a "sword" and interlinked. The goal is to remove all nine rings from the "sword". 

Attaching and removing the rings must follow two rules: 1. The first (rightmost) ring can be attached or removed at any time. 2. If the $k$-th ring is not removed and all rings to the right of the $k$-th ring have been removed, then the $(k+1)$-th ring (the ring immediately to the left of the $k$-th ring) can be attached or removed arbitrarily. Unlike the Rubik's Cube with its myriad variations, the optimal strategy for the Nine Linked Rings is unique. For simplicity, we take the four-ring case as an example to demonstrate the process. Here, 1 means the ring is on the "sword", and 0 means the ring has been removed. The initial state is 1111, and the operations at each step are as follows: 1. 1101 (according to rule 2, remove the 2nd ring). 2. 1100 (according to rule 1, remove the 1st ring). 3. 0100 (according to rule 2, remove the 4th ring). 4. 0101 (according to rule 1, attach the 1st ring). 5. 0111 (according to rule 2, attach the 2nd ring). 6. 0110 (according to rule 1, remove the 1st ring). 7. 0010 (according to rule 2, remove the 3rd ring). 8. 0011 (according to rule 1, attach the 1st ring). 9. 0001 (according to rule 2, remove the 2nd ring). 10. 0000 (according to rule 1, remove the 1st ring). Thus, removing the four-ring set requires at least $10$ steps. As the number of rings increases, the required number of steps also increases. For example, removing nine rings requires at least $341$ steps. Please compute, for $n$ rings, the minimum number of steps required to remove all rings under the rules.

The first line contains an integer $m$, the number of test cases. The next $m$ lines each contain an integer $n$.

Output $m$ lines, each containing the result for the corresponding test case.

For 10% of the testdata, $1 \le n \le 10$. For 30% of the testdata, $1 \le n \le 30$. For 100% of the testdata, $1 \le n \le 10^5$, $1 \le m \le 10$. Translated by ChatGPT 5