Alternating Sequence Number

This problem involves a sequence where the first number is \(1\) and each subsequent number is generated by alternating between multiplying the previous number by \(2\) and adding \(1\) to it. More formally, the sequence \(a_n\) is defined as:

\(a_1 = 1\), and for \(n \ge 1\):

\(a_{n+1} = \begin{cases} 2 \times a_n, & \text{if } n \text{ is odd}\\ a_n + 1, & \text{if } n \text{ is even} \end{cases}\)

Your task is to compute the \(N\)th number in this sequence for each test case provided as input.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(T\), the number of test cases. Each of the next \(T\) lines contains one integer \(N\) that denotes the position in the sequence.

outputFormat

For each test case, output the \(N\)th number of the sequence on a new line to standard output (stdout).

## sample

4
3
5
7
8

3
7
15
30

</p>