Roundgod is about to attend Gaokao (National Unified Examination for Admissions to General Universities and Colleges) and his dream school is Zhejiang University. He sees an interesting problem while he is studying Math, which is a problem related to Pascal’s Triangle.

The definition of Pascal’s Triangle is given below:

The first element and the last element of each row in Pascal’s Triangle is $1$, and the $m$th element of the $n$th row equals to the sum of the $m$th and the $(m-1)$th element of the $(n-1)$th row. Here’s an example of a 5 levels Pascal’s Triangle .

$$ \begin{gathered} 1\\ 1\quad1\\ 1\quad2\quad1\\ 1\quad3\quad3\quad1\\ 1\quad4\quad6\quad4\quad1 \end{gathered} $$

In the task, Roundgod is required to calculate how many elements in the $126$th row of Pascal’s Triangle are odd numbers.

After solving it, Roundgod thinks of a harder version of this problem. He gives you many requests about similar questions but the row number will be bigger. Please calculate that how many elements in the $k$th row of Pascal’s Triangle are odd numbers.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1\le T\le500$), indicating the number of test cases. For each test case:

The first and only line contains an integer $K$ ($K\le10^{18}$), indicating the required row number in Pascal’s Triangle.

Output

For each test case, output the number of odd numbers in the $k$th line.

Examples

Input 1

3
3
4
5

Output 1

2
4
2