The Baguenaudier is a traditional Chinese puzzle. As shown in the figure, nine rings are looped onto a "sword" and are interconnected. The goal of the game is to remove all nine rings from the "sword".
The manipulation of the rings must follow two rules:
- The first ring (the one on the far right) can be attached or removed at any time.
- If the $k$-th ring has not been removed, and all rings to the right of the $k$-th ring have been removed, then the $(k+1)$-th ring (the ring adjacent to the left of the $k$-th ring) can be attached or removed.
Unlike the Rubik's Cube, the optimal strategy for the Baguenaudier is unique. For simplicity, let's take the "four-ring" case to demonstrate the process. Here, $1$ represents a ring on the "sword", and $0$ represents a ring that has been removed.
The initial state is $1111$. The steps are as follows:
- $1101$ (Rule 2, remove the 2nd ring)
- $1100$ (Rule 1, remove the 1st ring)
- $0100$ (Rule 2, remove the 4th ring)
- $0101$ (Rule 1, attach the 1st ring)
- $0111$ (Rule 2, attach the 2nd ring)
- $0110$ (Rule 1, remove the 1st ring)
- $0010$ (Rule 2, remove the 3rd ring)
- $0011$ (Rule 1, attach the 1st ring)
- $0001$ (Rule 2, attach the 2nd ring)
- $0000$ (Rule 1, remove the 1st ring)
Thus, it takes at least $10$ steps to remove the "four-ring" puzzle. As $n$ increases, the number of steps required also increases. For example, removing the nine-ring puzzle requires at least $341$ steps.
Please calculate the minimum number of steps required to remove all $n$ rings according to the rules.
Input
The first line of the input contains an integer $m$, representing the number of test cases. The following $m$ lines each contain an integer $n$.
Output
The output contains $m$ lines, each representing the calculation result for the corresponding test case.
Examples
Input 1
3 3 5 9
Output 1
5 21 341
Constraints
- For $10\%$ of the data, $1 \le n \le 10$.
- For $30\%$ of the data, $1 \le n \le 30$.
- For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 10$.